当前位置:   article > 正文

【动态规划】零基础解决路径问题(C++)

【动态规划】零基础解决路径问题(C++)

目录

62.路径问题

解法(动态规划):

1. 状态表⽰:

2. 状态转移⽅程:

3. 初始化:

4. 填表顺序:

5. 返回值:

不同路径2.0

解法(动态规划):

1. 状态表⽰:

2. 状态转移:

3. 初始化:

4. 填表顺序:

5. 返回值:

代码

剑指Offer47.礼物的最⼤价值

方程;

代码:

931.下降路径最小和

 代码:

64.最小路径和 

【困难题】 174.地下城游戏(视频讲解)

总结:


62.路径问题

解法(动态规划):

算法思路:

1. 状态表⽰:

对于这种「路径类」的问题,我们的状态表⽰⼀般有两种形式:

  • i. [i, j] 位置出发,巴拉巴拉;
  • ii. 从起始位置出发,到达[i, j] 位置,巴拉巴拉。

这⾥选择第⼆种定义状态表⽰的⽅式: dp[i][j] 表⽰:⾛到[i, j] 位置处,⼀共有多少种⽅式。

2. 状态转移⽅程:

简单分析⼀下。如果dp[i][j] 表⽰到达[i, j] 位置的⽅法数,那么到达[i, j] 位置之 前的⼀⼩步,有两种情况:

  • i. 从[i, j] 位置的上⽅( [i - 1, j] 的位置)向下⾛⼀步,转移到[i, j] 位置;
  • ii. 从[i, j] 位置的左⽅( [i, j - 1] 的位置)向右⾛⼀步,转移到[i, j] 位置。

由于我们要求的是有多少种⽅法,因此状态转移⽅程就呼之欲出了: dp[i][j] = dp[i - 1] [j] + dp[i][j - 1] 。

3. 初始化

可以在最前⾯加上⼀个「辅助结点」,帮助我们初始化。使⽤这种技巧要注意两个点:

  • i. 辅助结点⾥⾯的值要「保证后续填表是正确的」;
  • ii. 「下标的映射关系」

在本题中,「添加⼀⾏」,并且「添加⼀列」后,只需将dp[0][1] 的位置初始化为1 即可。

4. 填表顺序:

根据「状态转移⽅程」的推导来看,

填表的顺序就是「从上往下」填每⼀⾏,在填写每⼀⾏的时候 「从左往右」。

5. 返回值:

根据「状态表⽰」,我们要返回dp[m][n] 的值。

代码:

  1. class Solution
  2. {
  3. public:
  4. int uniquePaths(int m, int n)
  5. {
  6. vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0)); // 创建⼀个 dp表
  7. dp[0][1] = 1; // 初始化
  8. // 填表
  9. for (int i = 1; i <= m; i++) // 从上往下
  10. for (int j = 1; j <= n; j++) // 从左往右
  11. dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
  12. // 返回结果
  13. return dp[m][n];
  14. }
  15. };

测试:

不同路径2.0

解法(动态规划):

算法思路:

本题为不同路径的变型,只不过有些地⽅有「障碍物」,只要在「状态转移」上稍加修改就可解决。

1. 状态表⽰:

对于这种「路径类」的问题,我们的状态表⽰⼀般有两种形式:

  • i. [i, j] 位置出发,巴拉巴拉;
  • ii. 从起始位置出发,到达[i, j] 位置,巴拉巴拉。

这⾥选择第⼆种定义状态表⽰的⽅式: dp[i][j] 表⽰:⾛到[i, j] 位置处,⼀共有多少种⽅式。

2. 状态转移:

简单分析⼀下。如果dp[i][j] 表⽰到达[i, j] 位置的⽅法数,那么到达[i, j] 位置之 前的⼀⼩步,有两种情况:

  • i. 从[i, j] 位置的上⽅( [i - 1, j] 的位置)向下⾛⼀步,转移到[i, j] 位置;
  • ii. 从[i, j] 位置的左⽅( [i, j - 1] 的位置)向右⾛⼀步,转移到[i, j] 位置。
  • 但是, [i - 1, j] 与[i, j - 1] 位置都是可能有障碍的,此时从上⾯或者左边是不可能 到达[i, j] 位置的,也就是说,此时的⽅法数应该是0。 

由此我们可以得出⼀个结论,只要这个位置上「有障碍物」,那么我们就不需要计算这个位置上的 值,直接让它等于0 即可。

3. 初始化:

可以在最前⾯加上⼀个「辅助结点」,帮助我们初始化。使⽤这种技巧要注意两个点:

  • i. 辅助结点⾥⾯的值要「保证后续填表是正确的」;
  • ii. 「下标的映射关系」

在本题中,「添加⼀⾏」,并且「添加⼀列」后,只需将dp[0][1] 的位置初始化为1 即可。

4. 填表顺序:

根据「状态转移⽅程」的推导来看,

填表的顺序就是「从上往下」填每⼀⾏,在填写每⼀⾏的时候 「从左往右」。

5. 返回值:

根据「状态表⽰」,我们要返回dp[m][n] 的值。

代码

  1. class Solution {
  2. public:
  3. int uniquePathsWithObstacles(vector<vector<int>>& ob) {
  4. // 1. 创建 dp 表
  5. // 2. 初始化
  6. // 3. 填表
  7. // 4. 返回值
  8. int m = ob.size(), n = ob[0].size();
  9. vector<vector<int>> dp(m + 1, vector<int>(n + 1));
  10. dp[1][0] = 1;
  11. for (int i = 1; i <= m; i++)
  12. for (int j = 1; j <= n; j++)
  13. if (ob[i - 1][j - 1] == 0)
  14. dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
  15. return dp[m][n];
  16. }
  17. };

测试:

剑指Offer47.礼物的最⼤价值

方程;

对于dp[i][j] ,我们发现想要到达[i, j] 位置,有两种⽅式:

  • i. 从[i, j] 位置的上⽅[i - 1, j] 位置,向下⾛⼀步,此时到达[i, j] 位置能 拿到的礼物价值为dp[i - 1][j] + grid[i][j] ;
  • ii. 从[i, j] 位置的左边[i, j - 1] 位置,向右⾛⼀步,此时到达[i, j] 位置能 拿到的礼物价值为dp[i][j - 1] + grid[i][j] 

我们要的是最⼤值,因此状态转移⽅程为: dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + grid[i][j] 。

代码:

  1. class Solution {
  2. public:
  3. int jewelleryValue(vector<vector<int>>& frame) {
  4. // 1. 创建 dp 表
  5. // 2. 初始化
  6. // 3. 填表
  7. // 4. 返回结果
  8. int m = frame.size(), n = frame[0].size();
  9. vector<vector<int>> dp(m + 1, vector<int>(n + 1));
  10. for (int i = 1; i <= m; i++)
  11. for (int j = 1; j <= n; j++)
  12. dp[i][j] =
  13. max(dp[i - 1][j], dp[i][j - 1]) + frame[i - 1][j - 1];
  14. return dp[m][n];
  15. }
  16. };

测试:

931.下降路径最小和

 代码:

  1. class Solution {
  2. public:
  3. int minFallingPathSum(vector<vector<int>>& matrix) {
  4. // 1. 创建 dp 表
  5. // 2. 初始化
  6. // 3. 填表
  7. // 4. 返回结果
  8. int n = matrix.size();
  9. vector<vector<int>> dp(n + 1, vector<int>(n + 2, INT_MAX));
  10. // 初始化第⼀⾏
  11. for (int j = 0; j < n + 2; j++)
  12. dp[0][j] = 0;
  13. for (int i = 1; i <= n; i++)
  14. for (int j = 1; j <= n; j++)
  15. dp[i][j] =
  16. min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i - 1][j + 1])) +
  17. matrix[i - 1][j - 1];//每次只能min两个
  18. int ret = INT_MAX;
  19. for (int j = 1; j <= n; j++)
  20. ret = min(ret, dp[n][j]);
  21. return ret;
  22. }
  23. };

64.最小路径和

代码:

  1. class Solution {
  2. public:
  3. int minPathSum(vector<vector<int>>& grid) {
  4. int m = grid.size(), n = grid[0].size();
  5. vector<vector<int>> dp(m + 1, vector<int>(n + 1, INT_MAX));
  6. dp[0][1] = dp[1][0] = 0;
  7. for (int i = 1; i <= m; i++)
  8. for (int j = 1; j <= n; j++)
  9. dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i - 1][j - 1];
  10. return dp[m][n];
  11. }
  12. };

【困难题】 174.地下城游戏(视频讲解)

恶魔们抓住了公主并将她关在了地下城 dungeon 的 右下角 。地下城是由 m x n 个房间组成的二维网格。我们英勇的骑士最初被安置在 左上角 的房间里,他必须穿过地下城并通过对抗恶魔来拯救公主。

骑士的初始健康点数为一个正整数。如果他的健康点数在某一时刻降至 0 或以下,他会立即死亡。

有些房间由恶魔守卫,因此骑士在进入这些房间时会失去健康点数(若房间里的值为负整数,则表示骑士将损失健康点数);其他房间要么是空的(房间里的值为 0),要么包含增加骑士健康点数的魔法球(若房间里的值为正整数,则表示骑士将增加健康点数)。

为了尽快解救公主,骑士决定每次只 向右 或 向下 移动一步。

返回确保骑士能够拯救到公主所需的最低初始健康点数。

注意:任何房间都可能对骑士的健康点数造成威胁,也可能增加骑士的健康点数,包括骑士进入的左上角房间以及公主被监禁的右下角房间。

代码:

  1. class Solution {
  2. public:
  3. int calculateMinimumHP(vector<vector<int>>& dungeon) {
  4. if (dungeon.empty() || dungeon[0].empty()) {
  5. return 0;
  6. }
  7. int m = dungeon.size(), n = dungeon[0].size();
  8. vector<vector<int>> dp(m + 1, vector<int>(n + 1, INT_MAX));
  9. dp[m][n-1] = dp[m-1][n] = 1; //假设为1,因为后面要取正数的
  10. for (int i = m - 1; i >= 0; --i) {
  11. for (int j = n - 1; j >= 0; --j) {
  12. int minHealth = min(dp[i+1][j], dp[i][j+1]) - dungeon[i][j];
  13. dp[i][j] = max(1, minHealth);
  14. }
  15. }
  16. return dp[0][0];
  17. }
  18. };

困难题还是有困难的原因的qwq

leetcode 地下城游戏 的一个问题理解

还有一点就是 dp[m][n-1] = dp[m-1][n] = 1

可以理解为他救完公主之后还要有一点血,才能活着

总结:

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/凡人多烦事01/article/detail/641293
推荐阅读
相关标签
  

闽ICP备14008679号