Leetcode: Unique Paths II

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.

与Unique Path, Minimum Path Sum题目解法类似，都是DP问题。建立一个新的矩阵，矩阵每个元素记录的是从upper left到该点的路径数。与Unique Path不同的是：写递归式的时候，能不能代入下一层递归需要检验obstacleGrid里该点是不是一个obstacle，如果是，该层返回0且不继续递归

一维DP解法：

 1 public class Solution {
 2     public int uniquePathsWithObstacles(int[][] obstacleGrid) {
 3         int[][] grid = obstacleGrid;
 4         int xLen = grid.length;
 5         if (xLen==0) return 0;
 6         int yLen = grid[0].length;
 7         if (yLen==0) return 0;
 8         
 9         int[] path = new int[yLen];
10         if (grid[0][0]==1)
11             return 0;
12         else path[0] = 1;
13         for (int i=1;i<yLen;i++)
14            if (grid[0][i]==1) path[i]=0;
15            else path[i] = path[i-1];
16         
17         for (int i=1;i<xLen;i++){
18             if (grid[i][0]==1) path[0] = 0;
19             for (int j=1;j<yLen;j++)
20                 if (grid[i][j]==1) path[j] = 0;
21                 else path[j] = path[j-1]+path[j];
22         }
23         return path[yLen-1];              
24         
25     }
26 }

Iteration方法：21-26行可删，因为如果那里是obstacle，那里在res矩阵里也是0，加它也无妨

 1 public class Solution {
 2     public int uniquePathsWithObstacles(int[][] obstacleGrid) {
 3         int m = obstacleGrid.length;
 4         int n = obstacleGrid[0].length;
 5         int[][] res = new int[m][n];
 6         for (int k=0; k<n; k++) {
 7             if (obstacleGrid[0][k] != 1) {
 8                 res[0][k] = 1;
 9             }
10             else break;
11         }
12         for (int t=0; t<m; t++) {
13             if (obstacleGrid[t][0] != 1) {
14                 res[t][0] = 1;
15             }
16             else break;
17         }
18         for (int i=1; i<m; i++) {
19             for (int j=1; j<n; j++) {
20                 if (obstacleGrid[i][j] == 1) continue;
21                 else {
22                     res[i][j] = res[i-1][j] + res[i][j-1];
23                 }
24             }
25         }
26         return res[m-1][n-1];
27     }
28 }