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.

这道题和上面那道只是多了一个障碍物的选择问题

思路是一样的，递推关系式也是一样的paths[i][j] = paths[i - 1][j] + paths[i][j - 1]。注意控制边界条件，和有障碍物时候paths的计算。

还要注意paths[i][j]和obstacleGrid[][]下标的对应关系，搞清楚了对应关系做起来就事半功倍了

 1 public class Solution {
 2     public int uniquePathsWithObstacles(int[][] obstacleGrid) {
 3         int paths[][] = new int[obstacleGrid.length + 1][obstacleGrid[0].length + 1];
 4         if(obstacleGrid[0][0] == 1)
 5             paths[1][1] = 0;
 6         else 
 7             paths[1][1] = 1;
 8         
 9         for(int i = 1; i < paths.length; i++){
10             for(int j = 1; j < paths[0].length; j++){
11                 if(i == 1 && j != 1){
12                     if(obstacleGrid[i - 1][j - 1] != 1)
13                         paths[i][j] = paths[i][j - 1];
14                     else
15                         paths[i][j] = 0;
16                 }//if
17                 if(j == 1 && i != 1){
18                     if(obstacleGrid[i - 1][j - 1] != 1)
19                         paths[i][j] = paths[i - 1][j];
20                     else
21                         paths[i][j] = 0;
22                 }//if
23                 if(i != 1 && j != 1){
24                     if(obstacleGrid[i - 1][j - 1] == 1)
25                         paths[i][j] = 0;
26                     else
27                         paths[i][j] = paths[i - 1][j] + paths[i][j - 1];
28                 }
29             }//for
30         }//for
31         
32         return paths[obstacleGrid.length][obstacleGrid[0].length];
33     }
34 }