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.

与, 题目解法类似，都是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

 

 

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