上海微网站公司,西安网站设计,驾校推广网络营销方案,网页制作设计思路和过程描述文章目录 题目描述算法原理1.状态表示#xff08;题目经验#xff09;2.状态转移方程3.初始化4.填表顺序5.返回值 代码实现CJava 题目描述
题目链接#xff1a;LCR 166.珠宝的最高价值
算法原理
1.状态表示#xff08;题目经验#xff09;
对于这种路径类的问题… 文章目录 题目描述算法原理1.状态表示题目经验2.状态转移方程3.初始化4.填表顺序5.返回值 代码实现CJava 题目描述
题目链接LCR 166.珠宝的最高价值
算法原理
1.状态表示题目经验
对于这种路径类的问题我们的状态表示⼀般有两种形式
从 [i, j] 位置出发…从起始位置出发到达 [i, j] 位置…
这⾥选择第⼆种定义状态表示的方式 dp[i][j] 表示⾛到 [i, j] 位置处此时珠宝的最大价值。
2.状态转移方程
根据最近的一步划分问题。对于 dp[i][j] 我们发现想要到达 [i, j] 位置有两种⽅式
从 [i, j] 位置的上⽅ [i - 1, j] 位置向下⾛⼀步此时到达 [i, j] 位置能 拿到的礼物价值为 dp[i - 1][j] frame[i][j] 从 [i, j] 位置的左边 [i, j - 1] 位置向右⾛⼀步此时到达 [i, j] 位置能 拿到的礼物价值为 dp[i][j - 1] frame[i][j]
我们要的是最⼤值因此状态转移方程为
dp[i][j] max(dp[i - 1][j], dp[i][j - 1]) frame[i - 1][j - 1];3.初始化
可以在最前⾯加上⼀个辅助结点帮助我们初始化。使⽤这种技巧要注意两个点
辅助结点⾥⾯的值要保证后续填表是正确的下标的映射关系。
在本题中添加一行并且添加⼀列后所有的值都为 0 即可。
4.填表顺序
根据状态转移方程填表的顺序是从上往下填写每一行每一行从左往右。
5.返回值
根据状态表示我们应该返回 dp[m][n] 的值。
代码实现
C
class Solution {
public:int jewelleryValue(vectorvectorint frame) {//1.创建一个dp表int m frame.size(), n frame[0].size();vectorvectorint dp(m 1,vectorint(n 1));//2.初始化//3.填表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];//4.返回值return dp[m][n];}
};Java
class Solution {public int jewelleryValue(int[][] frame) {// 1. 创建 dp 表// 2. 初始化// 3. 填表// 4. 返回值int m frame.length, n frame[0].length;int[][] dp new int[m 1][n 1];for (int i 1; i m; i)for (int j 1; j n; j)dp[i][j] Math.max(dp[i][j - 1], dp[i - 1][j]) frame[i - 1][j - 1];return dp[m][n];}
}
