leetCode 63 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]
]

这个题和1差不多，递推公式也是一样的，就是要处理一下有障碍物。。
但是，为什么要写这个题呢，就是做的时候有个地方没注意：就是第0行和第0列。如果没有障碍物，所有路径都是1，但是如果有障碍物。从第一个有障碍物开始，这一排和这一列以后的所有路径是0，就是以后的地方都到不了。。
就是要先把dp所有的地方都填上0.。遍历第一列和第一行的时候。遇到有障碍的地方就break,那剩下的地方都是0了。

 1 public class Solution {
 2     public int uniquePathsWithObstacles(int[][] obstacleGrid) {
 3         if(obstacleGrid==null || obstacleGrid.length==0)
 4             return 0;
 5         int m=obstacleGrid.length;
 6         int n=obstacleGrid[0].length;
 7         int[][] dp=new int[m][n]; //dp[i][j]表示从start到[i,j]位置不同路径条
          // 不需要初始化，默认初始化。
 8         //for(int i=0;i<m;i++)
 9            // for(int j=0;j<n;j++)
10                //dp[i][j]=0;
11         for(int i=0;i<n;i++)   //第一行障碍处理
12         {
13             if(obstacleGrid[0][i]!=1)
14                 dp[0][i]=1;
15             else
16                 break;
17         }
18             
19         for(int j=0;j<m;j++)   //第一列障碍处理
20         {
21             if(obstacleGrid[j][0]!=1)
22                 dp[j][0]=1;
23             else
24                 break;
25         }
26         for(int i=1;i<m;i++)
27             for(int j=1;j<n;j++)
28             {
29                 if(obstacleGrid[i][j]==1)   //如果该位置是障碍，则到达该点的路径条数为0
30                     dp[i][j]=0;
31                 else
32                     dp[i][j]=dp[i-1][j]+dp[i][j-1];
33             }        
34         return dp[m-1][n-1];
35     }
36 }

第11行－16行也可以写，如果没有障碍，后一个等于前一个：dp[i]=dp[i-1]是1; 如果有障碍就是默认值（初始化就是0）。如果再遇到没障碍的情况，还是后一个等于前一个还是0。

 1  dp[0][0] = 1;  
 2          for(int i = 1; i < n; i++){  
 3             if(obstacleGrid[0][i] == 1)  
 4                  dp[0][i] = 0;  
 5              else 
 6                  dp[0][i] = dp[0][i-1];  
 7          }  
 8 
 9 或者
10 
11  dp[0][0] = 1;  
12          for(int i = 1; i < n; i++){  
13             if(obstacleGrid[0][i] != 1)  
14                  dp[0][i] = dp[0][i-1];  
15          }