[LeetCode] 다른 경로 II
5799 단어 LeetCode
고전적인 동적 기획 문제, 더 많은 연습 1.삼각형 최소 경로 및https://blog.csdn.net/fmuma/article/details/80167433 2. 행렬 최소 경로 및https://blog.csdn.net/fmuma/article/details/80168120 3. 다른 경로https://blog.csdn.net/Fmuma/article/details/80172453
제목.
다른 경로 II
묘사
로봇은 m x n 메쉬의 왼쪽 상단 모서리에 있습니다(시작점은 다음 그림에서 Start로 표시됨).
로봇은 매번 아래로 또는 오른쪽으로 한 걸음만 이동할 수 있다.로봇이 메쉬의 오른쪽 아래 구석에 도달하려고 한다(아래 그림에서 "Finish"로 표시됨).
지금 격자 안에 장애물이 있다는 것을 고려하다.그러면 왼쪽 상단에서 오른쪽 하단까지 몇 개의 다른 경로가 있습니까?
그물 속의 장애물과 빈 위치는 각각 1과 0으로 표시한다.
설명: m와 n의 값은 모두 100을 넘지 않는다.
사고의 방향
여전히 동태적인 기획 문제이다. 이번 문제의 업그레이드는 서로 다른 경로의 업그레이드 버전으로 장애물이 하나 더 생겼기 때문에 그림을 그리고 분석하는 것은 비교적 간단하다.장애물이 있는 칸에 대해서는 첫 줄이나 열에 있으면 뒤에 있는 칸도 못 가요. 제가 못 가게 한 칸의 수치는 0이에요.서로 다른 경로와 같은 사고방식이라면 우리가 이동해야 하는 점에 대해 말하자면 현재 점의 이전 점과 왼쪽 점의 값을 얻기만 하면 된다. 그리고 덧붙여 전제는 현재 칸에 장애물이 있는지 판단해야 한다.
코드
package com.wy.LeetCode;
public class T63 {
public static void main(String[] args) {
int [][]arr = {{0,0,0},{0,1,0},{0,0,0}};
System.out.println(T63.uniquePathsWithObstacles(arr));
}
public static int uniquePathsWithObstacles(int[][] obstacleGrid) {
int m = obstacleGrid.length;
int n = obstacleGrid[0].length;
if(m==0||n==0){
return 0;
}
// , 0
if(obstacleGrid[0][0]==1){
return 0;
}
//
int [][]dp = new int[m][n];
dp[0][0] = 1;
// obstacleGrid 1
for(int i=1;iif(obstacleGrid[i][0]==1){//
for(int j=i;j0] = 0;
}
break;
}else{
dp[i][0] = 1;
}
}
//
for(int i=1;iif(obstacleGrid[0][i]==1){
for(int j=i+1;j0][j] = 0;
}
break;
}else{
dp[0][i] = 1;
}
}
// ,
for(int i=1;ifor(int j=1;jif(obstacleGrid[i][j]==1){
dp[i][j] = 0;
}else{
dp[i][j] = dp[i-1][j]+dp[i][j-1];
}
}
}
//
// for(int i=0;i
// for(int j=0;j
// System.out.print(dp[i][j]+" ");
// }
// System.out.println();
// }
return dp[m-1][n-1];
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
python 문자열 입력으로 모든 유효한 IP 주소 생성(LeetCode 93번 문제)이 문제의 공식 난이도는 Medium으로 좋아요 1296, 반대 505, 통과율 35.4%를 눌렀다.각 항목의 지표로 말하자면 보기에는 약간 규범에 맞는 것 같지만, 실제로도 확실히 그렇다.이 문제의 해법과 의도는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.