制作钓鱼网站的费用,设计杂志官网,wordpress怎么设置广告位,黄页网站推广app咋做广告本专栏内容为#xff1a;算法学习专栏#xff0c;分为优选算法专栏#xff0c;贪心算法专栏#xff0c;动态规划专栏以及递归#xff0c;搜索与回溯算法专栏四部分。 通过本专栏的深入学习#xff0c;你可以了解并掌握算法。 #x1f493;博主csdn个人主页#xff1a;小… 本专栏内容为算法学习专栏分为优选算法专栏贪心算法专栏动态规划专栏以及递归搜索与回溯算法专栏四部分。 通过本专栏的深入学习你可以了解并掌握算法。 博主csdn个人主页小小unicorn ⏩专栏分类动态规划专栏 代码仓库小小unicorn的代码仓库 关注我带你学习编程知识 专题二 题目来源题目描述题目解析算法原理1.状态表示2.状态转移方程3.初始化4.填表顺序5.返回值 代码实现 题目来源
本题来源为 Leetcode LCR 166. 珠宝的最高价值 题目描述
现有一个记作二维矩阵 frame 的珠宝架其中 frame[i][j] 为该位置珠宝的价值。拿取珠宝的规则为
1.只能从架子的左上角开始拿珠宝 2.每次可以移动到右侧或下侧的相邻位置 3.到达珠宝架子的右下角时停止拿取
注意珠宝的价值都是大于 0 的。除非这个架子上没有任何珠宝比如 frame [[0]]。
题目解析
我们以这个示例来模拟一下
算法原理
1.状态表示
经验题目要求
对于本题而言就是
dp[i][j]表示走到[i,j]位置的时候此时的最大价值
2.状态转移方程
还是分两种情况
因此状态方程为
dp[i][j]max(dp[i-1][j],dp[i][j-1])grid[i-1][j-1];3.初始化 4.填表顺序
从上往下填每一行每一行从左往右
5.返回值
返回dp[m][n];
代码实现
动态规划的代码基本就是固定的四步
1.创建dp表
2.初始化
3.填表
4.返回值本题完整代码实现
class Solution
{
public:int jewelleryValue(vectorvectorint ob) {//int mob.size(),nob[0].size();//创建dp表vectorvectorint dp(m1,vectorint(n1));//填表for(int i1;im;i){for(int j1;jn;j){//抄状态转移方程dp[i][j]max(dp[i-1][j],dp[i][j-1])ob[i-1][j-1]; }}return dp[m][n];}
};时间复杂度O(MN) 空间复杂度O(MN)
