DifferentPathsII题目描述：一个机器人位于mxn网格的左上角（下图中起点标记为“Start”）。机器人一次只能向下或向右移动一步。机器人尝试到达网格的右下角（下图中标记为“完成”）。现在考虑网格中有障碍物。那么从左上角到右下角会有多少条不同的路径呢？例子见LeetCode官网。来源：LeetCode链接：https://leetcode-cn.com/probl...版权归LeetCode所有。商业转载请联系官方授权，非商业转载请注明出处。解法一：递归法首先，经过分析可知，最后一步到达任意一个单元格可以来自于格子的左侧，也可以来自于格子的顶部，所以达到的步数任何一个格子，其左边的步数都加到它上面格子的步数总和上，所以可以用递归的方法求解。具体过程如下：如果m等于1或者n等于1，直接返回1；如果不满足以上条件，则递归调用方法solvesuniquePaths(m-1,n)+uniquePaths(m,n-1)。说明：与LeetCode-062-不同路径的区别在于，当左路径或上路径为0时（即路径失败时），只需要继续向一个方向递归即可。方案二：迭代法先记录第一行列中格子的移动，从第一个元素开始判断。如果第一个元素的值为1（即有障碍物），则为0，然后给后面的列赋值时，需要判断前一个元素和当前位置是否同时存在障碍物。然后根据columns迭代得到下面每一行对应的移动，迭代过程如下：先根据上一行第一个元素的值和中是否有障碍物得到columns[0]的值当前行的第一个元素；然后重复上面的过程，给列后面的元素赋值。赋值的时候需要判断前一个元素的值和当前位置是否有障碍物。最后，返回列的最后一个元素的值作为最后一步。说明：求解过程类似LeetCode-062-不同的路径，特别注意当第一个元素为1时，将不起作用；当只有一个元素且为0时，返回1表示有路可走，而不是返回0。publicclassLeetCode_063{/***递归法**@paramobstacleGrid*@return*/publicstaticintuniquePathsWithObstacles(int[][]obstacleGrid){intm=obstacleGrid.length,n=obstacleGrid[0].length;如果(m==1&&n==1){如果(obstacleGrid[m-1][n-1]==1){返回0;}else{返回1;}}if(obstacleGrid[m-1][n-1]==1){返回0;}returnuniquePathsWithObstacles(obstacleGrid,obstacleGrid.length-1,obstacleGrid[0].length-1);}privatestaticintuniquePathsWithObstacles(int[][]obstacleGrid,intx,inty){if(obstacleGrid[x][y]==1){返回0;}if(x==0&&y==0){if(obstacleGrid[x][y]==1){返回0;}else{返回1;}}如果(x>0){如果(y>0){如果(obstacleGrid[x-1][y]==1){如果(obstacleGrid[x][y-1]==1){返回0;}else{returnuniquePathsWithObstacles(obstacleGrid,x,y-1);}}else{if(obstacleGrid[x][y-1]==1){returnuniquePathsWithObstacles(obstacleGrid,x-1,y);}else{returnuniquePathsWithObstacles(obstacleGrid,x-1,y)+uniquePathsWithObstacles(obstacleGrid,x,y-1);}}}else{if(obstacleGrid[x-1][y]==1){返回0;}else{returnuniquePathsWithObstacles(obstacleGrid,x-1,y);}}}else{if(obstacleGrid[x][y-1]==1){返回0;}else{returnuniquePathsWithObstacles(obstacleGrid,x,y-1);}}}/***反代法**@paramobstacleGrid*@return*/publicstaticintuniquePathsWithObstacles2(int[][]obstacleGrid){intm=obstacleGrid.length,n=obstacleGrid[0].length;int[]列=newint[n];如果（obstacleGrid[0][0]==1）{列[0]=0；}else{列[0]=1;}//开始化第一步for(inti=1;i
