莆田市建设局网站,顺企网江西网站建设,网站开发代码编辑器,万网做网站怎么样1. 题目解析
题目链接#xff1a;LCR 166. 珠宝的最高价值 这个问题的理解其实相当简单#xff0c;只需看一下示例#xff0c;基本就能明白其含义了
2.算法原理
想象一下#xff0c;你正在玩一个寻宝游戏#xff0c;游戏地图是一个二维网格#xff0c;每个格子都藏有一…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(vectorvectorint frame) {int m frame.size(), 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], dp[i][j - 1]) frame[i - 1][j - 1];//减一细节}}return dp[m][n];}
};
The Last
嗯就是这样啦文章到这里就结束啦真心感谢你花时间来读。
觉得有点收获的话不妨给我点个赞吧
如果发现文章有啥漏洞或错误的地方欢迎私信我或者在评论里提醒一声~
