动态规划第二弹：路径类问题（不同路径，珠宝的最高价值，地下城游戏）
目录
前言
1. 不同路径
（1）题目及示例
（2）解题思路
（3）代码
2. 珠宝的最高价值
（1）题目及示例
（2）解题思路
（3）代码
3. 地下城游戏
（1） 题目及示例
（2）解题思路
（3）代码
前言
本文将讲解三道关于动态规划路径类型的题目，难度依次上升。解题思路部分图文并茂，希望对你有所启发。
1. 不同路径
（1）题目及示例
题目链接：62. 不同路径 - 力扣（LeetCode）
一个机器人位于一个
m x n网格的左上角 （起始点在下图中标记为 “Start” ）。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish” )。问总共有多少条不同的路径？
示例1：
输入：m = 3，n = 7
输出：28
示例2：
输入：m = 3, n = 2
输出：3
解释：从左上角开始，总共有 3 条路径可以到达右下角。
1. 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右
3. 向下 -> 向右 -> 向下
示例3：
输入：m = 3, n = 3
输出：6
（2）解题思路
如果使用动态规划来解题，就得先根据题目给出状态转移方程。根据以往的经验，都是以某个位置为结尾，来定义状态转移方程。
- 我们可以定义 dp[i][j] 表示，当机器人走到 (i，j) 位置时，一共有多少种方式。
- 下图中，当机器人走到三角的位置，他只可能从上面和左边走到该位置，而上面和左边位置的总的路径数量分别是 dp[i][j-1] 和 dp[i-1][j]。那么三角位置路径数量就是上面和左边位置路径数量之和。即 dp[i][j] = dp[i][j-1] + dp[i-1][j]。
这道题的核心部分已经讲完，接下来讲一下细节处理问题。
- 因为当前位置的dp值需要二维数组上面和左边的dp值进行赋值，所以第一行和第一列的元素，如果按照状态转移方程赋值，会发生越界。
- 但是第一行第一列的dp值手动初始化，就太麻烦。
- 因此，可以在原二维矩阵上，多加上一行和一列，从下标 (1, 1) 位置开始处理，就不会越界。
- 不过多加的一行和一列元素如何初始化，这需要根据题目来定。首先，(1, 1) 位置的dp值一定为1，所以它上面或者左边的元素其中一个初始化为1即可。剩下的元素全部初始化为0。
（3）代码
class Solution {
public:int uniquePaths(int m, int n) {// 创建dp表，多加一行和一列vector<vector<int>> dp(m + 1, vector<int>(n + 1)); // 初始化值dp[0][1] = 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][n];}
};2. 珠宝的最高价值
（1）题目及示例
题目链接：LCR 166. 珠宝的最高价值 - 力扣（LeetCode）
现有一个记作二维矩阵 frame 的珠宝架，其中 frame[i][j] 为该位置珠宝的价值。拿取珠宝的规则为：
- 只能从架子的左上角开始拿珠宝
- 每次可以移动到右侧或下侧的相邻位置
- 到达珠宝架子的右下角时，停止拿取
注意：珠宝的价值都是大于 0 的。除非这个架子上没有任何珠宝，比如 frame = [[0]]。
示例 1：
输入：frame = [ [1,3,1], [1,5,1], [4,2,1]]
输出：12
解释：路径 1→3→5→2→1 可以拿到最高价值的珠宝
（2）解题思路
这道题目跟不同路径类似，不过需要具体分析题目要求。
- 我们可以定义 dp[i][j] 表示，当从 (0, 0) 走到 (i，j) 位置时，珠宝最高价值的总数。
- 走到红色三角位置前，有两种方式，一种是从上面来，另外一种是从左边来，但是我们统计的是珠宝的最高价值，所以是比较 (i, j - 1) 和 (i - 1, j) 位置的珠宝价值，最后加上(i，j) 位置的珠宝价值。
- 所以状态转移方程为 dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]) + frame[i][j]。
状态转移方程分析写出来后，需要处理细节问题。
- 跟之前题目类似，第一行和第一列元素进行动态规划时，会越界。所以需要进行手动初始化，但是手动初始化比较麻烦。
- 因此，在原二维数组的基础上，多添加上一行和一列元素。
- 根据状态转移方程，全部初始化为0即可，这样不会影响原数组第一行第一列元素的赋值。
（3）代码
class Solution {
public:int jewelleryValue(vector<vector<int>>& frame) {// 创建dp表，多加上一行和一列int m = frame.size(), n = frame[0].size();// 默认初始化为0，所以不用单独赋值vector<vector<int>> dp(m + 1, vector<int>(n + 1));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];}
};3. 地下城游戏
（1） 题目及示例
题目链接：174. 地下城游戏 - 力扣（LeetCode）
恶魔们抓住了公主并将她关在了地下城 dungeon 的 右下角 。地下城是由 m x n 个房间组成的二维网格。我们英勇的骑士最初被安置在 左上角 的房间里，他必须穿过地下城并通过对抗恶魔来拯救公主。
骑士的初始健康点数为一个正整数。如果他的健康点数在某一时刻降至 0 或以下，他会立即死亡。
有些房间由恶魔守卫，因此骑士在进入这些房间时会失去健康点数（若房间里的值为负整数，则表示骑士将损失健康点数）；其他房间要么是空的（房间里的值为 0），要么包含增加骑士健康点数的魔法球（若房间里的值为正整数，则表示骑士将增加健康点数）。
为了尽快解救公主，骑士决定每次只 向右 或 向下 移动一步。返回确保骑士能够拯救到公主所需的最低初始健康点数。
注意：任何房间都可能对骑士的健康点数造成威胁，也可能增加骑士的健康点数，包括骑士进入的左上角房间以及公主被监禁的右下角房间。
示例1：
输入：dungeon = [ [-2,-3,3], [-5,-10,1], [10,30,-5]]
输出：7
解释：如果骑士遵循最佳路径：右 -> 右 -> 下 -> 下 ，则骑士的初始健康点数至少为 7 。
示例 2：
输入：dungeon = [[0]]
输出：1
（2）解题思路
这道题在Leetcode中难度是困难级别，我们尝试分析一下解题思路。
根据前两道做题经验，我们可以试着定义状态转移方程。定义 dp[i][j] 为从起点出发，到 (i，j) 位置结束，所需的最小健康点数。
- 在绿色三角 (i，j) 的位置，骑士可以从上面和左边走过来，那么需要上面和左边健康点数中的较小值，并减去当前房间的数值。
- 可是绿色房间的数值如果很小，就有可能导致健康点数变成负数。如果经过绿色房间后，健康点数大于0。
- 但是从(i，j) 的位置往下走或者往右走，可能会遇到房间数值是个很小的负数，导致绿色房间。
所以说，这种定义方式，写出的状态转移方程需要考虑后面的值。
从前往后的定义方式不行，我们可以换一种方式，从后往前。定义 dp[i][j] 为从(i，j) 位置开始，到终点右下角的房间结束，所需的最小健康点数。
- 骑士从绿色房间出发，可以往下面和右边的房间走，假设往右边的房间走，(i，j) 位置的健康点数加上该位置的数值，要大于等于(i，j - 1) 位置的健康点数。
- 即 dp[i][j] + d[i][j] >= dp[i][j - 1]，解一下不等式，dp[i][j] >= dp[i][j + 1] - d[i][j]。同理走下面的房间，也会得到类似的式子 dp[i][j] >= dp[i +1][j] - d[i][j]。
- 我们要的是健康点数的最小值，所以要取dp[i][j + 1]和dp[i + 1][j] 中的较小值。
- 最后，如果d[i][j]的数值是一个很大的整数，导致dp[i][j]变成负数,。因为骑士健康点数小于等于0的情况下无法继续走下去，所以需要改成最小健康点数1。
最后处理细节问题，这次我们填表的顺序是从下往上，从左往右。
因此，多加的一行和一列在后面。靠近原数组右下角位置的右边和下面的元素，需要初始化为1。其余的初始化为正无穷。
（3）代码
int calculateMinimumHP(vector<vector<int>>& d) {// 创建dp表，多加上一行和一列int m = d.size(), n = d[0].size();vector<vector<int>> dp(m + 1, vector<int>(n + 1, INT_MAX));// 初始化两个位置的值为1dp[m][n-1] = dp[m-1][n] = 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]) - d[i][j]);return dp[0][0];}创作充满挑战，但若我的文章能为你带来一丝启发或帮助，那便是我最大的荣幸。如果你喜欢这篇文章，请不吝点赞、评论和分享，你的支持是我继续创作的最大动力！
