目录
力扣题号：63. 不同路径 II - 力扣（LeetCode）
题目描述
示例
提示
思路
解法一：动态规划
（1）dp数组的下标及其含义
（2）确定递推公式
（3）初始化递推数组
（4）确定遍历顺序
（5）根据题意推出dp数组对照
障碍物处理
代码实现
总结
力扣题号：63. 不同路径 II - 力扣（LeetCode）
注：下述题目描述和示例均来自力扣
题目描述
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish”）。
现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？
网格中的障碍物和空位置分别用 1 和 0 来表示。
示例
示例 1：
输入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
输出：2
解释：3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径：
1. 向右 -> 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右 -> 向右
示例 2：
输入：obstacleGrid = [[0,1],[0,0]] 输出：1
提示
m == obstacleGrid.lengthn == obstacleGrid[i].length1 <= m, n <= 100-
obstacleGrid[i][j]为0或1
思路
解法一：动态规划
这道题的思路和不同路径（1）的思路其实并没有差太多，唯一的差别就是要增加一些代码用于处理中途的障碍物，使得这些有了不同。
（1）dp数组的下标及其含义
这里的dp[i][j] 都仍然是到达当前位置的路径数量。
（2）确定递推公式
在确定递推公式之前我们先观察一下问题，你会发现，第一行或者第一列的每一个位置都只有一种路径到达，因此你可以选择先把第一行和第一列全部赋值为 1，那么递推公式如下：
也就是到达当前位置只需要左边的点和右边的点的路径的和。
（3）初始化递推数组
在我们这里的话，初始化的内容还有一点多，就是将第一行和第一列都全部初始化为1.
（4）确定遍历顺序
思路都如此明确了，那么这个遍历顺序肯定是，从左到右从上到下了。
（5）根据题意推出dp数组对照
文章来源地址https://www.toymoban.com/news/detail-855932.html
障碍物处理
我们这里的障碍物处理涉及到了，一开始的m，n == 1的时候和后面的处理过程中。在一开始处理m，n的时候我们判断中途是否有障碍物，如果有的话直接返回0，没有就直接返回1。
如果是在初始化和中途的时候。先说初始化，初始化的时候我们将第一行和第一列进行遍历然后赋值为1，如果中途遇到了障碍物那么就停止赋值直接让它保持为0即可。
在中途的时候，如果该点是障碍物，那么直接跳过这个点。如果不是，那么判断左边和上面是否有障碍物，没有的话和之前一样
如果上面有障碍物，左边没有
如果左面有障碍物，上边没有
如果都有障碍物，直接等于0，当然了，你直接跳过这个点也可以
or
代码实现
class Solution {
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
// 获取m和n
int m = obstacleGrid.length;
int n = obstacleGrid[0].length;
// 如果只有一列，判断这一列中是否有障碍物
// 有返回0，没有返回1
if(n == 1 ){
for(int i = 0;i < m;i++){
if(obstacleGrid[i][0] == 1){
return 0;
}
}
return 1;
}
// 如果只有一行，判断这一行中是否有障碍物
// 有返回0，没有返回1
if(m == 1){
for(int i = 0;i < n;i++){
if(obstacleGrid[0][i] == 1){
return 0;
}
}
return 1;
}
// 定义出dp数组
int[][] dp = new int[m][n];
// 初始化一下dp数组
for(int i = 0; i < m; i++){
if(obstacleGrid[i][0] == 1){
// 有障碍物，下面去不了
break;
}
dp[i][0] = 1;
}
for(int i = 0; i < n; i++){
if(obstacleGrid[0][i] == 1){
// 有障碍物，右边去不了
break;
}
dp[0][i] = 1;
}
// 进入dp
for(int i = 1; i < m; i++){
for(int j = 1; j < n; j++){
// 跳过障碍物
if(obstacleGrid[i][j] == 1){
continue;
}
if(obstacleGrid[i - 1][j] == 1 && obstacleGrid[i][j - 1] == 1){
// 上边和左边都堵死了
dp[i][j] = 0;
// continue;
}else if(obstacleGrid[i - 1][j] == 1 && obstacleGrid[i][j - 1] == 0){
// 左边没堵死，上边堵死了
dp[i][j] = dp[i][j - 1];
}else if(obstacleGrid[i - 1][j] == 0 && obstacleGrid[i][j - 1] == 1){
// 左边堵死，上边没堵死
dp[i][j] = dp[i - 1][j];
}else{
// 左边和上边都没有堵死
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
}
// 返回答案
return dp[m - 1][n - 1];
}
}没啥难度
总结
其实这道题也就是多了障碍物的处理，只要是理解并读懂了我前一篇文章，不同的路径一，这道题应该是没有任何问题了。前一篇文章的链接在下面了：
第九章动态规划——不同路径（一）-CSDN博客
最后，谢谢大家的观看，如果觉得满意的话，点个赞呗~~~
文章来源：https://www.toymoban.com/news/detail-855932.html
到了这里，关于第九章动态规划——不同路径（二）有障碍物的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
