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 }
转载于:https://www.cnblogs.com/hewx/p/4539758.html
