题目链接：leetcode礼物的最大价值
目录
题目解析：
算法原理
1.状态表示
2.状态转移方程
3.初始化
4.填表顺序
5.返回值
编写代码
题目解析：
题目让我们求怎样走才能可以拿到最高价值的珠宝
由题可得：
- 只能从架子的左上角开始拿珠宝
- 每次可以移动到右侧或下侧的相邻位置
- 到达珠宝架子的右下角时，停止拿取
我们用示例一来分析：
当我们沿着这条路径走的时候可以得到最大值：12
算法原理:
1.状态表示
先创建一个dp表
首先先思考dp表里面的值所表示的含义（是什么？）
dp[i]表示到达i拿到最高价值的珠宝
这种状态表示怎么来的？
1.经验+题目要求
用之前或者之后的状态，推导出dp[i][j]的值；
根据最近的最近的一步，来划分问题
经验：以i位置为结尾
题目让我们求到达右下角拿到最高价值的珠宝，那么这里我们可以dp[i][j]来表示。
所以这里我们用i*j表示右下角位置；
2.状态转移方程
dp[i][j]等于什么？
因为我们只能每次可以移动到右侧或下侧的相邻位置
所以到达i位置有两种情况：
第一种：从[i-1][j]到达i位置
我们这里只要知道到达[i-1][j]拿到最高价值的珠宝，再加上[i]位置的珠宝价值(cost[i][j])
就可以得到i位置拿到最高价值的珠宝（dp[i][j]）;
而“到达[i-1][j]拿到最高价值的珠宝”正好是我们的状态表示：dp[i-1][j]
第二种：从[i][j-1]到达i位置
我们这里只要知道到达[i][j-1]拿到最高价值的珠宝，再加上[i]位置的珠宝价值(cost[i][j])
就可以得到i位置拿到最高价值的珠宝（dp[i][j]）;
而“到达[i][j-1]拿到最高价值的珠宝”正好是我们的状态表示：dp[i][j-1]
总结这两种情况：
因为题目让我们求的是拿到最高价值的珠宝
所以这里我们要取这两种情况的最大值
dp[i][j]=max(dp[i-1][j]+dp[i][j-1])+cost[i][j]
3.初始化
(保证填表的时候不越界)
由我们的状态转移方程得：
在0行0列的时候越界，所以我们这里可以在m*n的外围多加1行1列，如图：
还有一个问题是：
我们要拿新增用来初始化的行和列要初始化为几呢？
这里我们需要注意的一点就是在dp[1][1]的时候，最大的珠宝价值就是他本身cost
所以我们只要在dp表里的dp[0][1]、dp[1][0]中任选一个
初始化为cost[0][0]就可以了
我们这里选择[0][1]初始化为cost[0][0]
4.填表顺序
（为了填写当前状态的时候，所需要的状态已经计算过了）
这里所需要的状态是：到达该位置的上面和左边位置的方式
所以填表顺序：
从上到下填写每一行
从左到右填写每一列
5.返回值
（根据题目要求和状态表示）
综上分析：
返回值为：dp[m][n];文章来源：https://www.toymoban.com/news/detail-775627.html
编写代码:
文章来源地址https://www.toymoban.com/news/detail-775627.html
class Solution {
public:
int jewelleryValue(vector<vector<int>>& frame) {
//1.创建dp表
//2.初始化
//3.填表
//4.返回结果
int n=frame.size();
int m=frame[0].size();
vector<vector<int>> dp(n+1,vector<int>(m+1));
for(int i=1;i<n+1;i++)
for(int j=1;j<m+1;j++)
dp[i][j]=max(dp[i-1][j],dp[i][j-1])+frame[i-1][j-1];
return dp[n][m];
}
};到了这里，关于【动态规划】07路径问题_礼物的最大价值_C++（medium）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
