物流公司官方网站建设方案,常德网站建设专业品牌,学校建设门户网站的好处,石家庄移动端网站建设文章目录 day39学习内容一、不同路径2.1、动态规划五部曲1.1.1、 确定dp数组#xff08;dp table#xff09;以及下标的含义1.1.2、确定递推公式1.1.3、 dp数组如何初始化1.1.4、确定遍历顺序1.1.5、计算并返回最终结果 1.2、代码 二、不同路径II2.1、动态规划五部曲2.1.1、 … 文章目录 day39学习内容一、不同路径2.1、动态规划五部曲1.1.1、 确定dp数组dp table以及下标的含义1.1.2、确定递推公式1.1.3、 dp数组如何初始化1.1.4、确定遍历顺序1.1.5、计算并返回最终结果 1.2、代码 二、不同路径II2.1、动态规划五部曲2.1.1、 确定dp数组dp table以及下标的含义2.1.2、确定递推公式初始状态状态转移方程这个方程的含义是 2.1.3、 dp数组如何初始化2.1.4、确定遍历顺序2.1.5、计算并返回最终结果 2.2、代码2.2.1、obstacleGrid[m - 1][n - 1] 1为什么这句代码表示有障碍物 总结1.感想2.思维导图 day39学习内容 day39主要内容 不同路径不同路径II 声明 本文思路和文字引用自《代码随想录》
一、不同路径
509.原题链接
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
70.原题链接
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)位置有障碍物那么到达该位置的路径数量为0dp[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.思维导图 本文思路引用自代码随想录感谢代码随想录作者。-
