小叶-duck个人主页❄️个人专栏《Data-Structure-Learning》《C入门到进阶自我学习过程记录》《算法题讲解指南》--优选算法《算法题讲解指南》--递归、搜索与回溯算法《算法题讲解指南》--动态规划算法✨未择之路不须回头已择之路纵是荆棘遍野亦作花海遨游目录9.最小路径和题目链接题目描述题目示例解法(动态规划)算法思路C算法代码算法总结及流程解析10.地下城游戏题目链接题目描述题目示例解法(动态规划)算法思路C算法代码算法总结及流程解析结束语9.最小路径和题目链接64. 最小路径和 - 力扣LeetCode题目描述题目示例解法(动态规划)算法思路像这种表格形式的动态规划是非常容易得到「状态表示」以及「状态转移方程」的可以归结到「不同路径」一类的题里面。1.状态表示对于这种路径类的问题我们的状态表示一般有两种形式i.从[ij]位置出发巴拉巴拉;ii.从起始位置出发到达[ij]位置巴拉巴拉。这里选择第二种定义状态表示的方式dp[i][j]表示到达[ij]位置处最小路径和是多少。2.状态转移:简单分析一下。如果dp[i][j]表示到达到达[ij]位置处的最小路径和那么到达[ij]位置之前的一小步有两种情况i.从[i-1j]向下走一步转移到[ij]位置;ii.从[ij-1]向右走一步转移到[ij]位置。由于到[ij]位置两种情况并且我们要找的是最小路径因此只需要这两种情况下的最小值再加上[ij]位置上本身的值即可。也就是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(vectorvectorint grid) { //1、创建 dp 表 //2、初始化 //3、填表 //4、返回值 int m grid.size(); int n grid[0].size(); vectorvectorint dp(m 1, vectorint(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.状态表示这道题如果我们定义成:从起点开始到达[ij]位置的时候所需的最低初始健康点数。那么我们分析状态转移的时候会有一个问题:那就是我们当前的健康点数还会受到后面的路径的影响。也就是从上往下的状态转移不能很好地解决问题。这个时候我们要换一种状态表示:从[ij]位置出发到达终点时所需要的最低初始健康点数。这样我们在分析状态转移的时候后续的最佳状态就已经知晓。综上所述定义状态表示为dp[i][j]表示从[ij]位置出发到达终点时所需的最低初始健康点数。2.状态转移方程对于dp[i][j]从[ij]位置出发下一步会有两种选择(为了方便理解设dp[i][j]的最终答案是x ):i.走到右边然后走向终点那么我们在[ij]位置的最低健康点数加上这一个位置的消耗应该要大于等于右边位置的最低健康点数也就是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.走到下边然后走向终点那么我们在[ij]位置的最低健康点数加上这一个位置的消耗应该要大于等于下边位置的最低健康点数也就是: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(vectorvectorint dungeon) { //1、创建 dp 表 //2、初始化 //3、填表 //4、返回值 int m dungeon.size(); int n dungeon[0].size(); vectorvectorint dp(m 1, vectorint(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)位置到终点的最低初始健康点数作为状态表示通过比较右方和下方路径需求确定转移方程并处理负值情况。希望大家能有所收获
《算法题讲解指南：动态规划算法--路径问题》--9.最小路径和，10.地下城游戏
小叶-duck个人主页❄️个人专栏《Data-Structure-Learning》《C入门到进阶自我学习过程记录》《算法题讲解指南》--优选算法《算法题讲解指南》--递归、搜索与回溯算法《算法题讲解指南》--动态规划算法✨未择之路不须回头已择之路纵是荆棘遍野亦作花海遨游目录9.最小路径和题目链接题目描述题目示例解法(动态规划)算法思路C算法代码算法总结及流程解析10.地下城游戏题目链接题目描述题目示例解法(动态规划)算法思路C算法代码算法总结及流程解析结束语9.最小路径和题目链接64. 最小路径和 - 力扣LeetCode题目描述题目示例解法(动态规划)算法思路像这种表格形式的动态规划是非常容易得到「状态表示」以及「状态转移方程」的可以归结到「不同路径」一类的题里面。1.状态表示对于这种路径类的问题我们的状态表示一般有两种形式i.从[ij]位置出发巴拉巴拉;ii.从起始位置出发到达[ij]位置巴拉巴拉。这里选择第二种定义状态表示的方式dp[i][j]表示到达[ij]位置处最小路径和是多少。2.状态转移:简单分析一下。如果dp[i][j]表示到达到达[ij]位置处的最小路径和那么到达[ij]位置之前的一小步有两种情况i.从[i-1j]向下走一步转移到[ij]位置;ii.从[ij-1]向右走一步转移到[ij]位置。由于到[ij]位置两种情况并且我们要找的是最小路径因此只需要这两种情况下的最小值再加上[ij]位置上本身的值即可。也就是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(vectorvectorint grid) { //1、创建 dp 表 //2、初始化 //3、填表 //4、返回值 int m grid.size(); int n grid[0].size(); vectorvectorint dp(m 1, vectorint(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.状态表示这道题如果我们定义成:从起点开始到达[ij]位置的时候所需的最低初始健康点数。那么我们分析状态转移的时候会有一个问题:那就是我们当前的健康点数还会受到后面的路径的影响。也就是从上往下的状态转移不能很好地解决问题。这个时候我们要换一种状态表示:从[ij]位置出发到达终点时所需要的最低初始健康点数。这样我们在分析状态转移的时候后续的最佳状态就已经知晓。综上所述定义状态表示为dp[i][j]表示从[ij]位置出发到达终点时所需的最低初始健康点数。2.状态转移方程对于dp[i][j]从[ij]位置出发下一步会有两种选择(为了方便理解设dp[i][j]的最终答案是x ):i.走到右边然后走向终点那么我们在[ij]位置的最低健康点数加上这一个位置的消耗应该要大于等于右边位置的最低健康点数也就是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.走到下边然后走向终点那么我们在[ij]位置的最低健康点数加上这一个位置的消耗应该要大于等于下边位置的最低健康点数也就是: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(vectorvectorint dungeon) { //1、创建 dp 表 //2、初始化 //3、填表 //4、返回值 int m dungeon.size(); int n dungeon[0].size(); vectorvectorint dp(m 1, vectorint(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)位置到终点的最低初始健康点数作为状态表示通过比较右方和下方路径需求确定转移方程并处理负值情况。希望大家能有所收获
