day39学习内容
day39主要内容
- 不同路径
- 不同路径II
声明
本文思路和文字，引用自《代码随想录》
一、不同路径
2.1、动态规划五部曲
1.1.1、 确定dp数组（dp table）以及下标的含义
- 表示从（0 ，0）出发，到(i, j) 有dp[i][j]条不同的路径。
1.1.2、确定递推公式
dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
1.1.3、 dp数组如何初始化
dp[i][0]一定都是1，因为从(0, 0)的位置到(i, 0)的路径只有一条，dp[0][j]同理。
1.1.4、确定遍历顺序
从前向后遍历，没啥好说的
1.1.5、计算并返回最终结果
return dp[m - 1][n - 1];
1.2、代码
class Solution {
public int uniquePaths(int m, int n) {
int[][] dp = new int[m][n];
for (int i = 0; i < m; i++) {
dp[i][0] = 1;
}
for (int i = 0; i < n; i++) {
dp[0][i] = 1;
}
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
return dp[m - 1][n - 1];
}
}
二、不同路径II
2.1、动态规划五部曲
2.1.1、 确定dp数组（dp table）以及下标的含义
- 表示从（0 ，0）出发，到(i, j) 有dp[i][j]条不同的路径。
2.1.2、确定递推公式
本题需要在没有障碍的时候进行推导。
递推公式是如何推导出来的？
动态规划问题的解决关键在于找出合适的状态表示和状态转移方程。在这个问题中，我们的目标是计算从网格的左上角到右下角的所有不同路径的数量，同时考虑到路径上可能存在障碍物。
定义dp[i][j]为到达网格中(i, j)位置的不同路径数量。这里，i和j分别表示目标位置的行和列索引。
初始状态
- 对于第一列
dp[i][0]，如果从(0, 0)到(i, 0)之间没有障碍物，那么只存在一条路径（一直向下），否则路径数为0。 - 对于第一行
dp[0][j]，如果从(0, 0)到(0, j)之间没有障碍物，那么只存在一条路径（一直向右），否则路径数为0。
状态转移方程
对于网格中的任意位置(i, j)（除了第一行和第一列），到达该位置的路径可以从两个方向来：从上面的位置(i-1, j)向下走一步，或者从左边的位置(i, j-1)向右走一步。因此，到达(i, j)位置的路径数量是这两个方向路径数量的和，但这只适用于没有障碍物的情况。如果(i, j)位置有障碍物，则到达该位置的路径数量为0。
因此，状态转移方程可以表示为：
if obstacleGrid[i][j] == 0:
dp[i][j] = dp[i-1][j] + dp[i][j-1]
else:
dp[i][j] = 0
这个方程的含义是：
- 如果
(i, j)位置没有障碍物（obstacleGrid[i][j] == 0），那么dp[i][j]（到达(i, j)的路径数量）等于从上面来的路径数量（dp[i-1][j]）加上从左边来的路径数量（dp[i][j-1]）。 - 如果
(i, j)位置有障碍物，那么到达该位置的路径数量为0（dp[i][j] = 0），因为不能通过障碍物。
2.1.3、 dp数组如何初始化
for (int i = 0; i < m && obstacleGrid[i][0] == 0; i++) {
dp[i][0] = 1;
}
for (int j = 0; j < n && obstacleGrid[0][j] == 0; j++) {
dp[0][j] = 1;
}
2.1.4、确定遍历顺序
从前向后遍历，没啥好说的
2.1.5、计算并返回最终结果
return dp[m - 1][n - 1];
2.2、代码
class Solution {
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
int m = obstacleGrid.length;
int n = obstacleGrid[0].length;
int[][] dp = new int[m][n];
if (obstacleGrid[m - 1][n - 1] == 1 || obstacleGrid[0][0] == 1) {
return 0;
}
for (int i = 0; i < m && obstacleGrid[i][0] == 0; i++) {
dp[i][0] = 1;
}
for (int j = 0; j < n && obstacleGrid[0][j] == 0; j++) {
dp[0][j] = 1;
}
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
dp[i][j] = (obstacleGrid[i][j] == 0) ? dp[i - 1][j] + dp[i][j - 1] : 0;
}
}
return dp[m - 1][n - 1];
}
}
2.2.1、obstacleGrid[m - 1][n - 1] == 1，为什么这句代码表示有障碍物
在这段代码中，obstacleGrid[m - 1][n - 1] == 1用于检查网格的右下角是否有障碍物。这是因为obstacleGrid是一个二维数组，其中m表示网格的行数，n表示网格的列数。
当obstacleGrid[m - 1][n - 1] == 1时，这表示网格的终点（即右下角的位置）存在障碍物，无法到达。由于问题的要求是计算从左上角到右下角的所有可能路径，如果终点本身就是障碍物，那么显然没有任何路径可以到达终点，因此在这种情况下直接返回0，表示没有可行的路径。
总结
1.感想
- 今天的2题，动态转移方程都好难想的出来。。。
2.思维导图
本文思路引用自代码随想录，感谢代码随想录作者。-
