63. Unique Paths II

문제

https://leetcode.com/problems/unique-paths-ii/description/

풀이

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;

        int[][] dp = new int[m][n];


        for(int i = 0; i < m; i++) {
            if(obstacleGrid[i][0] == 1) {
                break;
            }
            dp[i][0] = 1;
        }

        for(int i = 0; i < n; i++) {
            if(obstacleGrid[0][i] == 1) {
                break;
            }
            dp[0][i] = 1;
        }

        for(int i = 1; i < m; i++) {
            for(int j = 1; j < n; j++) {
                if(obstacleGrid[i][j] == 1) {
                    dp[i][j] = 0;
                } else {
                    dp[i][j] = dp[i-1][j] + dp[i][j-1];
                }
            }
        }
         return dp[m-1][n-1]; 
    }
}

• 가능한 경로를 모두 탐색 -> DFS로 풀면 시간복잡도가 어마어마.. (O(2^N+M))
  • dp + memoization을 통해 빠르게 계산하기 O(N*M)
• obstacle이 있다면, dp[i][j] = 0
  • 없다면 obstacle에서 오는 경우는 어차피 0이므로 dp[i-1][j] + dp[i][j-1] 해도됨