【动态规划】路径问题

📝前言说明：

• 本专栏主要记录本人的基础算法学习以及LeetCode刷题记录，按专题划分
• 每题主要记录：（1）本人解法 + 本人屎山代码；（2）优质解法 + 优质代码；（3）精益求精，更好的解法和独特的思想（如果有的话）
• 文章中的理解仅为个人理解。如有错误，感谢纠错

🎬个人简介：努力学习ing
📋本专栏：C++刷题专栏
📋其他专栏：C语言入门基础，python入门基础，C++学习笔记，Linux
🎀CSDN主页 愚润泽

你可以点击下方链接，进行不同专题的动态规划的学习

点击链接	开始学习
斐波那契数列模型	路径问题

---

62. 不同路径

题目链接：https://leetcode.cn/problems/unique-paths/description/

个人解

思路：

• 状态表示：dp[i][j]：从 [0][0] 走到 [i][j] 的总路径数
• 状态转移方程：dp[i][j] = dp[i - 1][j] + dp[i][j - 1] (到一个格子，只能走左边或者上面的格子走下来)
• 初始化：dp[0][j] = 1; dp[i][0] = 1; 第一行和第一列都只有一种走法
• 填表顺序：从左往右，从上到下
• 返回值：dp[m - 1][n - 1]

用时：10:00
屎山代码：

class Solution {
public:int uniquePaths(int m, int n) {vector<vector<int>> dp(m, vector<int>(n, 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];}
};

时间复杂度：O($n\ast m$)
空间复杂度：O($n\ast m$)

---

62. 不同路径 II

题目链接：https://leetcode.cn/problems/unique-paths-ii/description/

个人解

思路：

• 和 62. 不同路径基本思路一样，不多说了
• 唯一需要注意的：要判断是否遇到障碍物
  • 遇到障碍物，则对应的dp[i] == 0
  • 并且初始化时，无法直接将第一行和第一列全部置为 1，因为可能出现障碍物
  • 此时，我们可以多dp开一行一列，用来做外层（全0），从而简化代码逻辑

屎山代码：

class Solution {
public:int uniquePathsWithObstacles(vector<vector<int>>& ob) {int m = ob.size(), n = ob[0].size();vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0)); // 多开上面一圈，方便处理边界dp[1][0] = 1; // 起点位置for(int i = 1; i <= m; i++)for(int j = 1; j <= n; j++)if(ob[i - 1][j - 1] == 0)dp[i][j] = dp[i - 1][j] + dp[i][j - 1];return dp[m][n];}
};

时间复杂度：O($m\ast n$)
空间复杂度：O($m\ast n$)

---

LCR 166. 珠宝的最高价值

题目链接：https://leetcode.cn/problems/li-wu-de-zui-da-jie-zhi-lcof/description/

个人解

思路：

    // dp 数组多开一行一列（便于处理边界）// dp[i][j] : 从 frame[0][0] 到 frame[i - 1][j - 1] 能拿到的最大价值// dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + frame[i - 1][j - 1]// 初始化：dp 全部初始化为0; dp[1][1] = frame[0][0]（初始位置初始化）// 填表顺序，按下标顺序填// 返回值：dp[m][n]

用时：13:00
屎山代码：

class Solution {
public:int jewelleryValue(vector<vector<int>>& frame) {int m = frame.size(), n = frame[0].size();vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));dp[1][1] = frame[0][0];for(int i = 1; i <= m; i++)for(int j = 1; j <= n; j++)dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + frame[i - 1][j - 1];return dp[m][n];}
};

时间复杂度：O($m\ast n$)
空间复杂度：O($m\ast n$)

---

931. 下降路径最小和

题目链接：https://leetcode.cn/problems/minimum-falling-path-sum/description/

个人解

思路：

    // 状态表示：dp[i][j] 表示从dp[0]行下降到第dp[i][j]这个位置的最小和// 状态转移方程：dp[i][j] = min(min(dp[i - 1][j - 1], dp[i - 1][j]), dp[i - 1][j + 1]) + matrix[i][j]// 初始化: dp[0] = matrix[0], 第一行直接赋值// 填表顺序：从上到下，从左到右// 返回值：dp[n - 1] 行的最小值// 细节：注意转移方程的越界情况【也可以多开一行和两列，并且把第一行设置成 全 0， 把旁边的两列设置成全 INT_MAX】

用时：10:00
屎山代码（通过）：

class Solution {
public:int minFallingPathSum(vector<vector<int>>& matrix) {int n = matrix.size();if(n == 1) return matrix[0][0]; // 处理特殊情况vector<vector<int>> dp(n, vector<int>(n, 0));for(int i = 0; i < n; i++)dp[0][i] = matrix[0][i]; // 初始化第一行for(int i = 1; i < n; i++){for(int j = 0; j < n; j++){if(j == 0)dp[i][j] = min(dp[i - 1][j], dp[i - 1][j + 1]) + matrix[i][j];else if(j == n - 1)dp[i][j] = min(dp[i - 1][j - 1], dp[i - 1][j]) + matrix[i][j];elsedp[i][j] = min(min(dp[i - 1][j - 1], dp[i - 1][j]), dp[i - 1][j + 1]) + matrix[i][j];}}int min = dp[n - 1][0];for(int i = 1; i < n; i++){if(dp[n - 1][i] < min)min = dp[n - 1][i];}return min;}
};

时间复杂度：O($n^2$)
空间复杂度：O($n^2$)

---

64. 最小路径和

题目链接：https://leetcode.cn/problems/minimum-path-sum/description/

个人解

思路：

    // 状态表示：dp[i][j] 从[0][0] 到 [i][j] 的最小路径和// 状态转移方程：dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j];（但这不是代码里写的，这是初步分析，因为后面初始化会多开dp）// 初始化：多开上面一行和左边一列，全部初始化为 INT_MAX，dp[0][0] = grid[0][0]// 填表顺序：从上到下，从左往右// 返回值：dp[m][n]

用时：10:00
屎山代码（通过，但是我感觉我写的特别不优雅）：

class Solution {
public:int minPathSum(vector<vector<int>>& grid) {int m = grid.size(), n = grid[0].size();vector<vector<int>> dp(m + 1, vector(n + 1, INT_MAX)); // 多出来的一行一列不能走dp[1][1] = grid[0][0]; // dp的下标对应关系是 +1for(int i = 1; i <= m; i++){for(int j = 1; j <= n; j++){if(i == 1 && j == 1) continue; // 跳过第一个初始化的位置dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i - 1][j - 1];}}return dp[m][n];}
};

时间复杂度：O($m\ast n$)
空间复杂度：O($m\ast n$)

---

174. 地下城游戏

题目链接：https://leetcode.cn/problems/dungeon-game/description/

---

优质解

思路：
这道题无法再以 dp[i][j] 为结尾，需要以dp[i][j]为起始点，从下往上。

• 状态表示：dp[i][j]表示：以 [i][i]为起点能够走到[m - 1][n - 1]（并走完了[m - 1][n - 1]）的[i][i]点需要的最小初始生命值
• 状态转移方程：dp[i][j] = min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j]
  • 细节问题：dp[i][j] 的血量 < 0骑士会挂，所以 dp[i][j] = max(1, dp[i][j])
• 初始化：多开下面一行和右边一列
  • dp[m][n - 1] 和 dp[m - 1][n]初始化为 1（因为dp[m - 1][n - 1]要它们初始化，1代表能走完最后一格）
  • 其他位置，初始化成INT_MAX，防止外面的一行一列被选
• 填表顺序：从下往上，从右往左
• 返回值：dp[0][0]

代码：

class Solution {
public:int calculateMinimumHP(vector<vector<int>>& dungeon) {int m = dungeon.size(), n = dungeon[0].size();vector<vector<int>> dp(m + 1, vector<int>(n + 1, INT_MAX));dp[m - 1][n] = 1; dp[m][n - 1] = 1;for(int i = m - 1; i >= 0; i--)for(int j = n - 1; j >=0; j--)dp[i][j] = max(1, min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j]);return dp[0][0];}
};

时间复杂度：O($m\ast n$)
空间复杂度：O($m\ast n$)

---

🌈我的分享也就到此结束啦🌈
要是我的分享也能对你的学习起到帮助，那简直是太酷啦！
若有不足，还请大家多多指正，我们一起学习交流！
📢公主，王子：点赞👍→收藏⭐→关注🔍
感谢大家的观看和支持！祝大家都能得偿所愿，天天开心！！！