leetcode解题: Unique Paths II (63)

发表于 | 分类于

Follow up for “Unique Paths”:

Now consider if some obstacles are added to the grids. How many unique paths would there be?

An obstacle and empty space is marked as 1 and 0 respectively in the grid.

For example,
There is one obstacle in the middle of a 3x3 grid as illustrated below.

[
[0,0,0],
[0,1,0],
[0,0,0]
]
The total number of unique paths is 2.

Note: m and n will be at most 100.

解法1：DP O(N^2) with O(N) 空间

是Unique Path的扩展，唯一区别是对于任意一个格子，要先判断是否为1，如果是1则有障碍物，在这种情况下，则到达这个
点的办法为0。其他地方的计算还是依照dp[i][j] = dp[i -1][j] + dp[i][j - 1]，这里同样用了滚动数组节省空间。
这题的坑是在： 一开始初始化数组的时候，对[0][i]的判断取决于[i][i - 1] 和那个格子是否有障碍物两个条件。不能仅根据当个格子来判断

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
    
    if (obstacleGrid == null || obstacleGrid.length == 0) {
        return 0;
    }
    
    int nrow = obstacleGrid.length;
    int ncol = obstacleGrid[0].length;
    
    int[] dp = new int[ncol];
    dp[0] = obstacleGrid[0][0] == 0?1:0;
    for (int j = 1; j < ncol; j++) {
        dp[j] = obstacleGrid[0][j] == 0?dp[j - 1]: 0;
    }
    
    for (int i = 1; i < nrow; i++) {
        dp[0] = obstacleGrid[i][0] == 0?dp[0] : 0;
        for (int j = 1; j < ncol; j++) {
            if (obstacleGrid[i][j] == 0) {
                dp[j] += dp[j - 1];
            } else {
                dp[j] = 0;
            }
        }
    }
    
    return dp[ncol - 1];    
}