《算法题讲解指南：动态规划算法--路径问题》--9.最小路径和，10.地下城游戏

🔥小叶-duck：个人主页

❄️个人专栏：《Data-Structure-Learning》《C++入门到进阶&自我学习过程记录》
《算法题讲解指南》--优选算法
《算法题讲解指南》--递归、搜索与回溯算法
《算法题讲解指南》--动态规划算法

✨未择之路，不须回头
已择之路，纵是荆棘遍野，亦作花海遨游

目录

9.最小路径和

题目链接：

题目描述：

题目示例：

解法(动态规划)：

算法思路：

C++算法代码：

算法总结及流程解析：

10.地下城游戏

题目链接：

题目描述：

题目示例：

解法(动态规划)：

算法思路：

C++算法代码：

算法总结及流程解析：

结束语

9.最小路径和

题目链接：

64. 最小路径和 - 力扣（LeetCode）

题目描述：

题目示例：

解法(动态规划)：

算法思路：

像这种表格形式的动态规划，是非常容易得到「状态表示」以及「状态转移方程」的，可以归结到「不同路径」一类的题里面。

1.状态表示：
对于这种路径类的问题，我们的状态表示一般有两种形式：
i.从[i，j]位置出发，巴拉巴拉;
ii.从起始位置出发，到达[i，j]位置，巴拉巴拉。
这里选择第二种定义状态表示的方式：
dp[i][j]表示：到达[i，j]位置处，最小路径和是多少。

2.状态转移:
简单分析一下。如果dp[i][j]表示到达到达[i，j]位置处的最小路径和，那么到达[i，j]位置之前的一小步，有两种情况：
i.从[i-1，j]向下走一步，转移到[i，j]位置;
ii.从[i，j-1]向右走一步，转移到[i，j]位置。
由于到[i，j]位置两种情况，并且我们要找的是最小路径，因此只需要这两种情况下的最小值，再加上[i，j]位置上本身的值即可。也就是：dp[i][j] = min(dp[i-1][j]，dp[i][j-1]) + grid[i][j]

3.初始化：
可以在最前面加上一个「辅助结点」，帮助我们初始化。使用这种技巧要注意两个点：
i，辅助结点里面的值要「保证后续填表是正确的」;
ii.「下标的映射关系」。
在本题中，「添加一行」，并且「添加一列」后，所有位置的值可以初始化为无穷大，然后让dp[0][1]=dp[1][0]= 1即可。

4.填表顺序：
根据「状态转移方程」的推导来看，填表的顺序就是「从上往下」填每一行，每一行「从左往后」。

5.返回值：
根据「状态表示」，我们要返回的结果是dp[m][n]。

C++算法代码：

class Solution { public: int minPathSum(vector<vector<int>>& grid) { //1、创建 dp 表 //2、初始化 //3、填表 //4、返回值 int m = grid.size(); int n = grid[0].size(); vector<vector<int>> dp(m + 1, vector<int>(n + 1, INT_MAX)); dp[0][1] = 0; //dp数组所有值初始化为最大值的目的是：避免额外扩展的边界值影响dp有效位置的值 for(int i = 1; i <= m; i++) { for(int j = 1; j <= n; j++) { dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i - 1][j - 1]; } } return dp[m][n]; } };

算法总结及流程解析：

10.地下城游戏

题目链接：

174. 地下城游戏 - 力扣（LeetCode）

题目描述：

题目示例：

解法(动态规划)：

算法思路：

1.状态表示：
这道题如果我们定义成:从起点开始，到达[i，j]位置的时候，所需的最低初始健康点数。
那么我们分析状态转移的时候会有一个问题:那就是我们当前的健康点数还会受到后面的路径的影响。也就是从上往下的状态转移不能很好地解决问题。
这个时候我们要换一种状态表示:从[i，j]位置出发，到达终点时所需要的最低初始健康点数。这样我们在分析状态转移的时候，后续的最佳状态就已经知晓。
综上所述，定义状态表示为：
dp[i][j]表示：从[i，j]位置出发，到达终点时所需的最低初始健康点数。

2.状态转移方程：
对于dp[i][j]，从[i，j]位置出发，下一步会有两种选择(为了方便理解，设dp[i][j]的最终答案是x ):
i.走到右边，然后走向终点：那么我们在[i，j]位置的最低健康点数加上这一个位置的消耗，应该要大于等于右边位置的最低健康点数，也就是：x+ dungeon[i][j]>=dp[i][j+ 1]。通过移项可得:x >= dp[i][j + 1]- dungeon[i][j] 。因为我们要的是最小值，因此这种情况下的x =dp[i][j+ 1]-dungeon[i][j]；
ii.走到下边，然后走向终点：那么我们在[i，j]位置的最低健康点数加上这一个位置的消耗，应该要大于等于下边位置的最低健康点数，也就是:x + dungeon[i][j]>= dp[i + 1][j]。通过移项可得:x >= dp[i+ 1][j]- dungeon[i][j] 。因为我们要的是最小值，因此这种情况下的x =dp[i+ 1][j]-dungeon[i][j]；
综上所述，我们需要的是两种情况下的最小值，因此可得状态转移方程为：dp[i][j] = min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j]
但是，如果当前位置的dungeon[i][j]是一个比较大的正数的话，dp[i][j]的值可能变成 0或者负数。也就是最低点数会小于1，那么骑士就会死亡。因此我们求出来的dp[i][j]如果小于等于的话，说明此时的最低初始值应该为1 。处理这种情况仅需让dp[i][j]与1取一个最大值即可：dp[i][j] = max(1, dp[i][j])

3.初始化：
可以在最前面加上一个「辅助结点」，帮助我们初始化。使用这种技巧要注意两个点：
i.辅助结点里面的值要「保证后续填表是正确的」;
ii.「下标的映射关系」。
在本题中，在dp表最后面添加一行，并且添加一列后，所有的值都先初始化为无穷大，然后让dp[m][n-1]=dp[m -1][n]=1即可。

4.填表顺序：
根据「状态转移方程」，我们需要「从下往上填每一行」，「每一行从右往左」。

5.返回值：
根据「状态表示」，我们需要返回dp[0][0]的值。

C++算法代码：

class Solution { public: int calculateMinimumHP(vector<vector<int>>& dungeon) { //1、创建 dp 表 //2、初始化 //3、填表 //4、返回值 int m = dungeon.size(); int n = dungeon[0].size(); vector<vector<int>> dp(m + 1, vector<int>(n + 1, INT_MAX)); dp[m - 1][n] = 1; //此时dp[i][j]表示：从[i][j]位置出发到达终点所需的最小点数 //dp[m - 1][n]这个虚拟位置初始化为1的目的是：确保最后到达终点减去终点值时能保留1不死 for(int i = m - 1; i >= 0; i--) { for(int j = n - 1; j >= 0; j--) { dp[i][j] = min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j]; dp[i][j] = max(1, dp[i][j]); //当取到1时说明dp[i][j]<=0，说明dungeon[i][j]是血包并且值很大 //就会导致当dp[i][j]为负数时也能到达终点， //但是不管在哪个位置只要血量小于等于0就失败，不可能为负数 //所以只需要dp[i][j]为最小满足活着的值1即可 } } return dp[0][0]; } };

算法总结及流程解析：

结束语

到此，9.最小路径和，10.地下城游戏 这两道算法题就讲解完了。最小路径和问题，采用从起点到(i,j)位置的最小路径和作为状态表示，通过比较上方和左方路径值确定状态转移方程，并利用辅助结点技巧初始化；地下城游戏，则采用从(i,j)位置到终点的最低初始健康点数作为状态表示，通过比较右方和下方路径需求确定转移方程，并处理负值情况。希望大家能有所收获！