目录
题目
题目解析
思路
1.状态表示
2.状态转移方程
3.初始化
4.填表顺序
5.返回值
代码
题目
LCR 166. 珠宝的最高价值
（现在leetcode上面是这个题）这个题跟下面这个题叙述方式一样，就拿下面这个 题来讲解）
题目描述：
在一个m*n的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于0）。你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格，直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值，请计算你最多能拿到多少价值的礼物？
示例1：
输入：[[1,3,1],[1,5,1],[4,2,1]]
输出：12
解释：路径1-3-5-2-1可以拿到最多价值的礼物
题目解析
用示例1 来举例：输入[[1,3,1],[1,5,1],[4,2,1]]，形成如下的一个3*3的矩阵，我们把这个二维矩阵叫cost矩阵，每个位置都是一个对应价值的礼物，要求我们拿到最多价值的礼物，那就意味着，要走最大的值
题目中说从左上角出发，每次可以向下走或者向右走，那个数值大往哪走，右下角为终点，
思路
1.状态表示
我们这里以某一个位置为结尾来确定状态表示，又根据题目要求，需要我们确定所走路径的拿到礼物的最大价值，所以状态表示dp[i][j]表示起点走到【i，j】位置，此时拿到礼物的最大价值。
2.状态转移方程
状态表示的经验就是根据最近的一步划分问题，那我们怎么到达【i，j】，第一种要么从左边向右走到【i，j】位置，要么从上边向下走到【i，j】位置
所以dp[i][j]可以有两种方式得来
a)从左边向右走：也就是从【i，j-1】位置走到【i，j】位置，然后拿到【i，j】位置的礼物价值，如果要起点到【i，j】位置拿到礼物的价值最大（dp[i][j])，就需要起点到【i，j-1】位置拿到礼物的价值最大(dp[i][j-1]),因此dp[i][j]=dp[i][j-1]+cost[i][j]。
b)从上边向下走：同理a，这个方式对应的状态转移方程为dp[i][j]=dp[i-1][j]+cost[i][j]。
最后取这两种情况的最大值就行
3.初始化
之前说过，初始化的目的就是为了让填表不越界，我们 首先要分析填哪些位置回越界，因为填表的时候是根据状态转移方程来填表的，状态转移方程
根据这两个公式计算后用最大的那个值填表，计算是一个位置需要这个位置上面的那个值，和这个位置左边的值，但是第一行没有上面的值，第一列没有左边的值。所以第一行和 第一列需要初始化
之前也讲过，虚拟 结点的初始化，虚拟结点就是在创建dp表的时候多创建一行和多创建一列，然后从【1，1】位置开始填表。
虚拟结点里面的值要确保dp表中填的值的准确性。所以填0是最合适的，相当于里面礼物的的价值为0。
4.填表顺序
从上至下，从左至右
5.返回值
因为多开了一行和一列，所以返回dp[m][n]就行。
代码
int jewelleryValue(int** frame, int frameSize, int* frameColSize)
{
//创建dp表
int dp[1000][1000]={0};
//初始化这个刚好全是0就不用初始化了
//行和列
int m=frameSize;
int n=frameColSize[0];
for(int i=1;i<m+1;i++){
for(int j=1;j<n+1;j++)
{
dp[i][j]=frame[i-1][j-1]+((dp[i-1][j]>dp[i][j-1])?dp[i-1][j]:dp[i][j-1]);
}
}
return dp[m][n];
}空间复杂度：O(mn)文章来源：https://www.toymoban.com/news/detail-840468.html
时间复杂度：O(mn)文章来源地址https://www.toymoban.com/news/detail-840468.html
到了这里，关于动态规划|【路径问题】礼物的最大价值（LCR 166.珠宝的最高价值）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
