63. Unique Paths II

# Medium

similar to #62

If grid[x][y] is blocked, sumPath[x][y] = 0

If grid[x][y] isn't blocked, sumPath[x][y]=sumPath[x-1][y]+sumPath[x][y-1]

Solution:

1. Initialize first row and first column of paths

2. compute other elements of paths

Python example:

Java

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length, n = obstacleGrid[0].length;
        int[][] paths = new int[m][n];
        if(obstacleGrid[0][0] == 1)
            paths[0][0] = 0;
        else
            paths[0][0] = 1;
        
        for(int i = 1; i < m; i ++) {
            if(obstacleGrid[i][0] == 1)
                paths[i][0] = 0;
            else
                paths[i][0] = paths[i-1][0];
        }
        for(int j = 1; j < n; j ++) {
            if(obstacleGrid[0][j] == 1)
                paths[0][j] = 0;
            else
                paths[0][j] = paths[0][j-1];
        }
        
        for(int row = 1; row < m; row ++)
            for(int col = 1; col < n; col ++) {
                if(obstacleGrid[row][col] == 1)
                    paths[row][col] = 0;
                else
                    paths[row][col] = paths[row-1][col] + paths[row][col-1];
            }
        
        return paths[m-1][n-1];
    }
}

Python

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        m = len(obstacleGrid)
        n = len(obstacleGrid[0])
        paths = [[0] * n for i in range(m)]

        for i in range(m):
            if obstacleGrid[i][0] != 1:
                paths[i][0] = 1
            else:
                break
                
        for j in range(n):
            if obstacleGrid[0][j] != 1:
                paths[0][j] = 1
            else:
                break
                
        print(paths)
        
        for i in range(1, m):
            for j in range(1, n):
                if obstacleGrid[i][j] == 1:
                    paths[i][j] = 0
                else:
                    paths[i][j] = paths[i-1][j] + paths[i][j-1]
                    
        return paths[-1][-1]

这道题思路简单，但是一次性不容易写对。考虑[[1,0]]的情况