一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？ 网格中的障碍物和空位置分别用 1 和 0 来表示。
说明：m 和 n 的值均不超过 100。
示例 1:
输入: [ [0,0,0], [0,1,0], [0,0,0] ] 输出: 2 解释: 3x3 网格的正中间有一个障碍物。 从左上角到右下角一共有 2 条不同的路径：
向右 -> 向右 -> 向下 -> 向下向下 -> 向下 -> 向右 -> 向右该题与62题不同的地方在于多了障碍物， 该题可以借助画图来理解，如图所示： X用来表示障碍物，图中每个格子的数值依然表示从该格子到达终点可走的路径数 我们可以看到，由于机器人只能向下或者向右走，所以对于最后一行和最后一列，障碍物前面的值只能为0 其他行和列还是按照 dp[i][j]=dp[i+1][j]+dp[i][j+1]来求，当遇到障碍物时，障碍物所对应的格子的数值置为0
class Solution { public int uniquePathsWithObstacles(int[][] obstacleGrid) { int m=obstacleGrid.length; int n=obstacleGrid[0].length; //先判断只有一行或者一列的情况，有障碍物返回0，没有就返回1 if(m==1||n==1){ for(int i=m-1;i>=0;i--){ for(int j=n-1;j>=0;j--){ if(obstacleGrid[i][j]==1) return 0; } } return 1; } //创建一个新的二维数组dp存储每个格子对应的路径数值 int[][] dp=new int[m][n]; boolean flag=false; //对最后一行赋值 for(int i=n-1;i>=0;i--){ if(obstacleGrid[m-1][i]==1) flag=true; if(!flag){ dp[m-1][i]=1; }else{ dp[m-1][i]=0; } } flag=false; //对最后一列赋值 for(int i=m-1;i>=0;i--){ if(obstacleGrid[i][n-1]==1) flag=true; if(!flag){ dp[i][n-1]=1; }else{ dp[i][n-1]=0; } } for(int i=m-2;i>=0;i--){ for(int j=n-2;j>=0;j--){ //遇到障碍物将对应的数值置为0 if(obstacleGrid[i][j]==1){ dp[i][j]=0; }else{ dp[i][j]=dp[i+1][j]+dp[i][j+1]; } } } return dp[0][0]; } }