63. 不同路径 II
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？
网格中的障碍物和空位置分别用 1 和 0 来表示。
示例 1：
- 输入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
- 输出：2 解释：
- 3x3 网格的正中间有一个障碍物。
- 从左上角到右下角一共有 2 条不同的路径：
- 向右 -> 向右 -> 向下 -> 向下
- 向下 -> 向下 -> 向右 -> 向右
示例 2：
- 输入：obstacleGrid = [[0,1],[0,0]]
- 输出：1
提示：
- m == obstacleGrid.length
- n == obstacleGrid[i].length
- 1 <= m, n <= 100
- obstacleGrid[i][j] 为 0 或 1
解决思路：
首先说一下还是使用动态规划来做，只不过这道题目里面加了障碍物，这里我在做的时候犯了一个错误，就是初始化的时候，如果第一行或者第一列已经出现1障碍物之后，那么就不可以再进行走下去了
刚开始我写的初始化的代码是：
//初始化第一列
for(int i = 0;i < row;i++){
if(obstacleGrid[i][0] == 1){
dp[i][0] = 0;
}else{
dp[i][0] = 1;
}
}
//初始化第一行
for(int i = 0;i < col;i++){
if(obstacleGrid[0][i] == 1){
dp[0][i] = 0;
}else{
dp[0][i] = 1;
}
}
这里明显是错误的。原因就是else的部分，如果遇到障碍物，则后续位置都无法到达，直接跳出循环就可以了。
具体的思路为：
- 创建一个二维数组
dp，其中dp[i][j]表示从起点到达网格(i, j)的不同路径数目。 - 初始化起点的路径数目为1，因为只有一种方式可以到达起点。
- 更新第一列的路径数目，如果这个格子没有障碍物，则该格子的路径数目为1。
- 更新第一行的路径数目，如果这个格子没有障碍物，则该格子的路径数目为1。
- 从左上角开始，逐行逐列计算路径数目。对于每个格子，如果该格子没有障碍物，则路径数目等于左侧格子的路径数目加上上方格子的路径数目。
- 如果如果该格子有障碍物，则直接跳过。
- 返回终点的路径数目作为最终的答案。
需要注意的是，如果某个格子上有障碍物，则该格子的路径数目为0，表示无法通过该格子。在代码中，我们通过判断 obstacleGrid[i][j] 是否为0来判断是否有障碍物。
代码实现：
/**
* 63. 不同路径 II
*/
public class UniquePathsII {
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
if (obstacleGrid == null || obstacleGrid.length == 0) {
return 0;
}
int row = obstacleGrid.length;
int col = obstacleGrid[0].length;
int[][] dp = new int[row][col];
// 初始化第一列
for (int i = 0; i < row; i++) {
if (obstacleGrid[i][0] == 0) {
dp[i][0] = 1;
} else {
// 如果遇到障碍物，则后续位置都无法到达，直接跳出循环
break;
}
}
// 初始化第一行
for (int i = 0; i < col; i++) {
if (obstacleGrid[0][i] == 0) {
dp[0][i] = 1;
} else {
// 如果遇到障碍物，则后续位置都无法到达，直接跳出循环
break;
}
}
for (int i = 1; i < row; i++) {
for (int j = 1; j < col; j++) {
if (obstacleGrid[i][j] == 1) {
// 障碍物位置的路径数设为0
dp[i][j] = 0;
} else {
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
}
return dp[row - 1][col - 1];
}
}
首先，我们可以用一个2D网格来表示给定的障碍物网格。其中0表示空地，1表示障碍物。我们需要计算从起点到终点的不同路径数目。
1.创建一个与给定网格相同大小的二维数组 dp，用于保存路径数目。
dp = [[0, 0, 0],
[0, 0, 0],
[0, 0, 0]]
2.更新第一列的路径数目。如果某个格子上方没有障碍物，则该格子的路径数目与上方格子的路径数目相同。否则，如果上方格子有障碍物，则无法通过该格子。
dp = [[1, 0, 0],
[1, 0, 0],
[1, 0, 0]]
3.更新第一行的路径数目。如果某个格子左侧没有障碍物，则该格子的路径数目与左侧格子的路径数目相同。否则，如果左侧格子有障碍物，则无法通过该格子。
dp = [[1, 1, 1],
[1, 0, 0],
[1, 0, 0]]
4.从左上角开始，逐行逐列计算路径数目。对于每个格子，如果该格子没有障碍物，则路径数目等于左侧格子的路径数目加上上方格子的路径数目。如果该格子有障碍物，则路径数目为0。
dp = [[1, 1, 1],
[1, 0, 1],
[1, 1, 2]]
5.终点的路径数目即为最终的答案。在这个例子中，终点的路径数目为2。
评论区