[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];
    }

}

좋은 웹페이지 즐겨찾기