本文主要是介绍【Leetcode每日一题】 动态规划 - LCR 166. 珠宝的最高价值（难度⭐⭐）（52），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
1. 题目解析
题目链接：LCR 166. 珠宝的最高价值
这个问题的理解其实相当简单，只需看一下示例，基本就能明白其含义了
2.算法原理
想象一下，你正在玩一个寻宝游戏，游戏地图是一个二维网格，每个格子都藏有一定价值的礼物。你的任务是从起点出发，找到一条路径，使得沿途收集到的礼物总价值最大。
1.设置状态表示
首先，我们需要一种方式来记录到达每个格子时的最大礼物价值。这里，我们用dp[i][j]来表示到达网格中第i行第j列这个格子时的最大礼物价值。
2.明确状态转移
想要知道到达某个格子的最大价值，我们需要看看从哪些格子可以到达这里。显然，我们可以从上面的格子[i-1, j]下来，也可以从左边的格子[i, j-1]过来。那么，到达当前格子的最大价值，就是从上面或左边过来时的最大价值，再加上当前格子的礼物价值。所以，我们可以得到状态转移方程：
dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + grid[i][j]
其中，grid[i][j]表示第i行第j列格子的礼物价值。
3.初始化工作
为了让状态转移能够顺利进行，我们需要对dp数组进行初始化。一种常用的技巧是在网格的上方和左侧各添加一行一列，并将这些辅助格子的值都设为0。这样做的好处是，当我们开始填表时，可以确保所有需要的状态都已经有了初始值。
4.填表顺序
接下来，我们要开始填表了。根据状态转移方程，我们应该从左上角开始，一行一行地往下填，每一行内又是从左到右地填。这样，当我们填到某个格子时，它上面和左边的格子都已经填好了，我们可以直接利用这些格子的值来进行状态转移。
5.找到答案
最后，当我们填完整个表格后，dp[m][n]的值就是我们想要找的答案，即从起点出发，到达网格右下角格子的最大礼物价值。
3.代码编写
class Solution
{
public:int jewelleryValue(vector<vector<int>>& frame) {int m = frame.size(), 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], dp[i][j - 1]) + frame[i - 1][j - 1];//减一细节}}return dp[m][n];}
};The Last
嗯，就是这样啦，文章到这里就结束啦，真心感谢你花时间来读。
觉得有点收获的话，不妨给我点个赞吧！
如果发现文章有啥漏洞或错误的地方，欢迎私信我或者在评论里提醒一声~
这篇关于【Leetcode每日一题】 动态规划 - LCR 166. 珠宝的最高价值（难度⭐⭐）（52）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
