《算法题讲解指南：动态规划算法--路径问题》--7.礼物的最大价值，8.下降路径最小和

🔥小叶-duck：个人主页

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

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

目录

7.礼物的最大价值

题目链接：

题目描述：

题目示例：

解法(动态规划)：

算法思路：

C++算法代码：

算法总结及流程解析：

8.下降路径最小和

题目链接：

题目描述：

题目示例：

C++算法代码：

算法总结及流程解析：

结束语

7.礼物的最大价值

题目链接：

LCR 166. 珠宝的最高价值 - 力扣（LeetCode）

题目描述：

题目示例：

解法(动态规划)：

算法思路：

1.状态表示：
对于这种「路径类」的问题，我们的状态表示一般有两种形式：
i.从[i，j]位置出发，巴拉巴拉;
ii.从起始位置出发，到达[i，j]位置，巴拉巴拉。
这里选择第二种定义状态表示的方式：
dp[i][j]表示:走到[i，j]位置处，此时的最大价值。

2.状态转移方程：
对于 dp[i][j]，我们发现想要到达[i，j]位置，有两种方式：
i.从[i，j]位置的上方[i - 1，j]位置，向下走一步，此时到达[i，j]位置能拿到的礼物价值为dp[i-1][j]+grid[i][j];
ii. 从[i，j]位置的左边[i，j-1]位置，向右走一步，此时到达[i，j]位置能拿到的礼物价值为 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(vector<vector<int>>& frame) { //1、创建 dp 表 //2、初始化 //3、填表 //4、返回值 int m = frame.size(); int n = frame[0].size(); 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] + frame[i - 1][j - 1], dp[i][j - 1] + frame[i - 1][j - 1]); } } return dp[m][n]; } };

算法总结及流程解析：

8.下降路径最小和

题目链接：

931. 下降路径最小和 - 力扣（LeetCode）

题目描述：

题目示例：

解法(动态规划)：

算法思路：

关于这一类题，由于我们做过类似的，因此「状态表示」以及「状态转移」是比较容易分析出的。比较难的地方可能就是对于「边界条件」的处理。

1.状态表示：
对于这种「路径类」的问题，我们的状态表示一般有两种形式：
i.从[i，j]位置出发，到达目标位置有多少种方式;
ii.从起始位置出发，到达[i，j]位置，一共有多少种方式
这里选择第二种定义状态表示的方式：
dp[i][j]表示:到达[i，j]位置时，所有下降路径中的最小和。

2.状态转移方程：
对于普遍位置[i，j]，根据题意得，到达[i，j]位置可能有三种情况：
i. 从正上方[i- 1，j]位置转移到[i，j]位置;
ii.从左上方[i- 1，j -1]位置转移到[i，j]位置;
iii.从右上方[i -1，j+ 1] 位置转移到[i，j]位置;
我们要的是三种情况下的「最小值」，然后再加上矩阵在[i，j]位置的值。于是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(vector<vector<int>>& matrix) { //1、创建 dp 表 //2、初始化 //3、填表 //4、返回值 int m = matrix.size(); int n = matrix[0].size(); vector<vector<int>> dp(m + 1, vector<int>(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)位置的最小和，状态转移考虑上方、左上方和右上方三个来源的最小值，同样使用辅助结点处理边界条件。希望大家能有所收获！