安徽网站设计哪家效果好,手机百度免费下载,微信公众平台注册官网入口,星巴克vi设计分析[动态规划] (七) 路径问题#xff1a;LCR 166./剑指offer 47. 珠宝的最高价值 文章目录 [动态规划] (七) 路径问题#xff1a;LCR 166./剑指offer 47. 珠宝的最高价值题目解析解题思路状态表示状态转移方程初始化和填表顺序 返回值代码实现总结 LCR 166. 珠宝的最高价值 题目…[动态规划] (七) 路径问题LCR 166./剑指offer 47. 珠宝的最高价值 文章目录 [动态规划] (七) 路径问题LCR 166./剑指offer 47. 珠宝的最高价值题目解析解题思路状态表示状态转移方程初始化和填表顺序 返回值代码实现总结 LCR 166. 珠宝的最高价值 题目解析
(1) 二维矩阵中存放的是每个珠宝的价值
(2) 从左上角取到右下角
(3) 只能向右或者向下移动
解题思路 状态表示
按照以往的经验dp[i] [j] 以ij位置为终点得到的珠宝总价值。
状态转移方程
以状态表示可以得出
dp(ij)取决于两个位置的价值dp(i-1j)和dp(i j-1)。
所以dp(ij)就等于它们两个的最大值再加上(ij)位置对应的价值。
所以
dp[i][j] max(dp[i-1][j], dp[i][j-1]) (ij)位置对应的价值初始化和填表顺序
初始化 初始化时只需要处理一下第一行和第一列的边界情况即可。
所以我们多开辟一列和一行蓝色格子又由于 dp(ij)就等于它们两个的最大值再加上(ij)位置对应的价值。所以我们只需要将多开辟的初始化为0即可。我们在创建dp数组时扩容后正好是0。
填表顺序
一列一列填表即可。
返回值
多开辟一列和一行返回dp[m] [n]即可。
看到这里大家可以先尝试实现代码再接下来看下面的内容。 代码实现
class Solution {
public:int jewelleryValue(vectorvectorint frame) {//创建dp数组int m frame.size(), n frame[0].size();vectorvectorint dp(m1, vectorint(n1));//初始化// dp[1][1] frame[0][0];//填表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];}
};总结
细节多开辟一列一行相当于我们将下标向右下方移动。所以最后在找原数组中对应位置行和列下标应该都进行减1。如frame[i-1] [j-1]。
