题目要求

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题目系列。关于Unique Path I请参考我的。相比于I，这里添加的需求是说，某些节点上存在路障。存在路障的节点会在数组中被标记为1。请问从起点到终点有多少条独立路径。

思路和代码

在Unique Path I的思路基础上，我们可以知道，如果某个节点上存在路障，那么任何从该节点前往终点的路径都将不存在。也就是说，该节点的路径数为0。在此基础上，我们可以知道，如果该节点为路障，则该节点路径数为0，否则该节点的路径数等于左侧节点路径数和上方节点路径数的和。代码如下：

public int uniquePathsWithObstacles(int[][] obstacleGrid) {        int row = obstacleGrid.length;        if(row==0){            return 0;        }        int column = obstacleGrid[0].length;                int path = obstacleGrid[0][0] == 1 ? 0 : 1;        for(int i = 1 ; i