小叶-duck个人主页❄️个人专栏《Data-Structure-Learning》《C入门到进阶自我学习过程记录》《算法题讲解指南》--优选算法《算法题讲解指南》--递归、搜索与回溯算法《算法题讲解指南》--动态规划算法✨未择之路不须回头已择之路纵是荆棘遍野亦作花海遨游目录7.礼物的最大价值题目链接题目描述题目示例解法(动态规划)算法思路C算法代码算法总结及流程解析8.下降路径最小和题目链接题目描述题目示例C算法代码算法总结及流程解析结束语7.礼物的最大价值题目链接LCR 166. 珠宝的最高价值 - 力扣LeetCode题目描述题目示例解法(动态规划)算法思路1.状态表示对于这种「路径类」的问题我们的状态表示一般有两种形式i.从[ij]位置出发巴拉巴拉;ii.从起始位置出发到达[ij]位置巴拉巴拉。这里选择第二种定义状态表示的方式dp[i][j]表示:走到[ij]位置处此时的最大价值。2.状态转移方程对于 dp[i][j]我们发现想要到达[ij]位置有两种方式i.从[ij]位置的上方[i - 1j]位置向下走一步此时到达[ij]位置能拿到的礼物价值为dp[i-1][j]grid[i][j];ii. 从[ij]位置的左边[ij-1]位置向右走一步此时到达[ij]位置能拿到的礼物价值为 dp[i][j-1]grid[i][j]我们要的是最大值因此状态转移方程为dp[i][j] max(dp[i - 1][j], dp[i][j - 1]) grid[i][j]。3.初始化可以在最前面加上一个「辅助结点」帮助我们初始化。使用这种技巧要注意两个点i.辅助结点里面的值要「保证后续填表是正确的」;ii.「下标的映射关系」。在本题中「添加一行」并且「添加一列」后所有的值都为即可。4.填表顺序:根据「状态转移方程」填表的顺序是「从上往下填写每一行」「每一行从左往右」。5.返回值:根据「状态表示」我们应该返回dp[m][n]的值。C算法代码class Solution { public: int jewelleryValue(vectorvectorint frame) { //1、创建 dp 表 //2、初始化 //3、填表 //4、返回值 int m frame.size(); int n frame[0].size(); vectorvectorint dp(m 1, vectorint(n 1)); for(int i 1; i m; i) { for(int j 1; j n; j) { dp[i][j] max(dp[i - 1][j] frame[i - 1][j - 1], dp[i][j - 1] frame[i - 1][j - 1]); } } return dp[m][n]; } };算法总结及流程解析8.下降路径最小和题目链接931. 下降路径最小和 - 力扣LeetCode题目描述题目示例解法(动态规划)算法思路关于这一类题由于我们做过类似的因此「状态表示」以及「状态转移」是比较容易分析出的。比较难的地方可能就是对于「边界条件」的处理。1.状态表示对于这种「路径类」的问题我们的状态表示一般有两种形式i.从[ij]位置出发到达目标位置有多少种方式;ii.从起始位置出发到达[ij]位置一共有多少种方式这里选择第二种定义状态表示的方式dp[i][j]表示:到达[ij]位置时所有下降路径中的最小和。2.状态转移方程对于普遍位置[ij]根据题意得到达[ij]位置可能有三种情况i. 从正上方[i- 1j]位置转移到[ij]位置;ii.从左上方[i- 1j -1]位置转移到[ij]位置;iii.从右上方[i -1j 1] 位置转移到[ij]位置;我们要的是三种情况下的「最小值」然后再加上矩阵在[ij]位置的值。于是dp[i][j] min(dp[i -1][j], min(dp[i - 1][j - 1], dp[i - 1][j 1])) matrix[i][j] 。3.初始化可以在最前面加上一个「辅助结点」帮助我们初始化。使用这种技巧要注意两个点i.辅助结点里面的值要「保证后续填表是正确的」;ii.「下标的映射关系」。在本题中需要「加上一行」并且「加上两列」。所有的位置都初始化为无穷大然后将第一行初始化为 0 即可。4.填表顺序根据「状态表示」填表的顺序是「从上往下」。5.返回值注意这里不是返回 dp[m][n]的值题目要求「只要到达最后一行」就行了因此这里应该返回「dp 表中最后一行的最小值」。C算法代码class Solution { public: int minFallingPathSum(vectorvectorint matrix) { //1、创建 dp 表 //2、初始化 //3、填表 //4、返回值 int m matrix.size(); int n matrix[0].size(); vectorvectorint dp(m 1, vectorint(n 2, INT_MAX)); //dp所有值初始化为INT_MAX是为了保证两边的边界值不会影响dp有效位置的结果 //dp的第一行初始化成0 for(int j 0; j n 2; j) { dp[0][j] 0; } for(int i 1; i m; i) { for(int j 1; j n; j) { dp[i][j] min(min(dp[i - 1][j - 1], dp[i - 1][j]), dp[i - 1][j 1]) matrix[i - 1][j - 1]; } } //判断dp最后一行所有数据的最小值 int ret INT_MAX;//避免ret本身值影响最终结果需避免取到ret则初始化成最大值 for(int j 0; j n 2; j) { ret min(ret, dp[m][j]); } return ret; } };算法总结及流程解析结束语到此7.礼物的最大价值8.下降路径最小和 这两道算法题就讲解完了。礼物的最大价值通过定义dp[i][j]表示到达(i,j)位置的最大价值状态转移方程为dp[i][j]max(dp[i-1][j],dp[i][j-1])grid[i][j]采用辅助结点技巧初始化并填表下降路径最小和定义dp[i][j]为到达(i,j)位置的最小和状态转移考虑上方、左上方和右上方三个来源的最小值同样使用辅助结点处理边界条件。希望大家能有所收获
《算法题讲解指南：动态规划算法--路径问题》--7.礼物的最大价值，8.下降路径最小和
发布时间：2026/7/26 4:09:55
小叶-duck个人主页❄️个人专栏《Data-Structure-Learning》《C入门到进阶自我学习过程记录》《算法题讲解指南》--优选算法《算法题讲解指南》--递归、搜索与回溯算法《算法题讲解指南》--动态规划算法✨未择之路不须回头已择之路纵是荆棘遍野亦作花海遨游目录7.礼物的最大价值题目链接题目描述题目示例解法(动态规划)算法思路C算法代码算法总结及流程解析8.下降路径最小和题目链接题目描述题目示例C算法代码算法总结及流程解析结束语7.礼物的最大价值题目链接LCR 166. 珠宝的最高价值 - 力扣LeetCode题目描述题目示例解法(动态规划)算法思路1.状态表示对于这种「路径类」的问题我们的状态表示一般有两种形式i.从[ij]位置出发巴拉巴拉;ii.从起始位置出发到达[ij]位置巴拉巴拉。这里选择第二种定义状态表示的方式dp[i][j]表示:走到[ij]位置处此时的最大价值。2.状态转移方程对于 dp[i][j]我们发现想要到达[ij]位置有两种方式i.从[ij]位置的上方[i - 1j]位置向下走一步此时到达[ij]位置能拿到的礼物价值为dp[i-1][j]grid[i][j];ii. 从[ij]位置的左边[ij-1]位置向右走一步此时到达[ij]位置能拿到的礼物价值为 dp[i][j-1]grid[i][j]我们要的是最大值因此状态转移方程为dp[i][j] max(dp[i - 1][j], dp[i][j - 1]) grid[i][j]。3.初始化可以在最前面加上一个「辅助结点」帮助我们初始化。使用这种技巧要注意两个点i.辅助结点里面的值要「保证后续填表是正确的」;ii.「下标的映射关系」。在本题中「添加一行」并且「添加一列」后所有的值都为即可。4.填表顺序:根据「状态转移方程」填表的顺序是「从上往下填写每一行」「每一行从左往右」。5.返回值:根据「状态表示」我们应该返回dp[m][n]的值。C算法代码class Solution { public: int jewelleryValue(vectorvectorint frame) { //1、创建 dp 表 //2、初始化 //3、填表 //4、返回值 int m frame.size(); int n frame[0].size(); vectorvectorint dp(m 1, vectorint(n 1)); for(int i 1; i m; i) { for(int j 1; j n; j) { dp[i][j] max(dp[i - 1][j] frame[i - 1][j - 1], dp[i][j - 1] frame[i - 1][j - 1]); } } return dp[m][n]; } };算法总结及流程解析8.下降路径最小和题目链接931. 下降路径最小和 - 力扣LeetCode题目描述题目示例解法(动态规划)算法思路关于这一类题由于我们做过类似的因此「状态表示」以及「状态转移」是比较容易分析出的。比较难的地方可能就是对于「边界条件」的处理。1.状态表示对于这种「路径类」的问题我们的状态表示一般有两种形式i.从[ij]位置出发到达目标位置有多少种方式;ii.从起始位置出发到达[ij]位置一共有多少种方式这里选择第二种定义状态表示的方式dp[i][j]表示:到达[ij]位置时所有下降路径中的最小和。2.状态转移方程对于普遍位置[ij]根据题意得到达[ij]位置可能有三种情况i. 从正上方[i- 1j]位置转移到[ij]位置;ii.从左上方[i- 1j -1]位置转移到[ij]位置;iii.从右上方[i -1j 1] 位置转移到[ij]位置;我们要的是三种情况下的「最小值」然后再加上矩阵在[ij]位置的值。于是dp[i][j] min(dp[i -1][j], min(dp[i - 1][j - 1], dp[i - 1][j 1])) matrix[i][j] 。3.初始化可以在最前面加上一个「辅助结点」帮助我们初始化。使用这种技巧要注意两个点i.辅助结点里面的值要「保证后续填表是正确的」;ii.「下标的映射关系」。在本题中需要「加上一行」并且「加上两列」。所有的位置都初始化为无穷大然后将第一行初始化为 0 即可。4.填表顺序根据「状态表示」填表的顺序是「从上往下」。5.返回值注意这里不是返回 dp[m][n]的值题目要求「只要到达最后一行」就行了因此这里应该返回「dp 表中最后一行的最小值」。C算法代码class Solution { public: int minFallingPathSum(vectorvectorint matrix) { //1、创建 dp 表 //2、初始化 //3、填表 //4、返回值 int m matrix.size(); int n matrix[0].size(); vectorvectorint dp(m 1, vectorint(n 2, INT_MAX)); //dp所有值初始化为INT_MAX是为了保证两边的边界值不会影响dp有效位置的结果 //dp的第一行初始化成0 for(int j 0; j n 2; j) { dp[0][j] 0; } for(int i 1; i m; i) { for(int j 1; j n; j) { dp[i][j] min(min(dp[i - 1][j - 1], dp[i - 1][j]), dp[i - 1][j 1]) matrix[i - 1][j - 1]; } } //判断dp最后一行所有数据的最小值 int ret INT_MAX;//避免ret本身值影响最终结果需避免取到ret则初始化成最大值 for(int j 0; j n 2; j) { ret min(ret, dp[m][j]); } return ret; } };算法总结及流程解析结束语到此7.礼物的最大价值8.下降路径最小和 这两道算法题就讲解完了。礼物的最大价值通过定义dp[i][j]表示到达(i,j)位置的最大价值状态转移方程为dp[i][j]max(dp[i-1][j],dp[i][j-1])grid[i][j]采用辅助结点技巧初始化并填表下降路径最小和定义dp[i][j]为到达(i,j)位置的最小和状态转移考虑上方、左上方和右上方三个来源的最小值同样使用辅助结点处理边界条件。希望大家能有所收获
