LeetCode刷题--- 珠宝的最高价值

个人主页：元清加油_【C++】,【C语言】,【数据结构与算法】-CSDN博客

个人专栏

力扣递归算法题

http://t.csdnimg.cn/yUl2I

【C++】

http://t.csdnimg.cn/6AbpV

数据结构与算法

http://t.csdnimg.cn/hKh2l

前言：这个专栏主要讲述动态规划算法，所以下面题目主要也是这些算法做的

我讲述题目会把讲解部分分为3个部分：
1、题目解析

2、算法原理思路讲解

3、代码实现

珠宝的最高价值

题目链接：珠宝的最高价值

题目

现有一个记作二维矩阵 frame 的珠宝架，其中 frame[i][j] 为该位置珠宝的价值。拿取珠宝的规则为：

只能从架子的左上角开始拿珠宝
每次可以移动到右侧或下侧的相邻位置
到达珠宝架子的右下角时，停止拿取

注意：珠宝的价值都是大于 0 的。除非这个架子上没有任何珠宝，比如 frame = [[0]]。

示例 1:

输入: frame = [[1,3,1],[1,5,1],[4,2,1]]
输出: 12
解释: 路径 1→3→5→2→1 可以拿到最高价值的珠宝

提示：

0 < frame.length <= 200
0 < frame[0].length <= 200

解法

题目解析

现有一个记作二维矩阵 frame 的珠宝架，其中 frame[i][j] 为该位置珠宝的价值。
只能从架子的左上角开始拿珠宝。
每次可以移动到右侧或下侧的相邻位置。
到达珠宝架子的右下角时，停止拿取。

输入: frame = [[1,3,1],[1,5,1],[4,2,1]]

输出: 12

解释: 路径 1→3→5→2→1 可以拿到最高价值的珠宝

算法原理讲解

我们这题使用动态规划，我们做这类题目可以分为以下五个步骤

状态显示
状态转移方程
初始化（防止填表时不越界）
填表顺序
返回值

状态显示

dp[i][j] 表示：⾛到 [i, j] 位置处，此时的最⼤价值。

状态转移方程

对于 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][j] 。

初始化（防止填表时不越界）

可以在最前⾯加上⼀个「辅助结点」，帮助我们初始化。使⽤这种技巧要注意两个点

辅助结点里面的值要「保证后续填表是正确的」。
「下标的映射关系」。

本题「添加⼀⾏」，并且「添加⼀列」后，所有的值都为 0 即可。

填表顺序

填表的顺序是「从上往下填写每⼀⾏」，「每⼀⾏从左往右」。

返回值

返回 dp[m][n] 的值。

代码实现

时间复杂度：O(mn)。
空间复杂度：O(mn) 或 O(n)，即为动态规划需要使用的空间。

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];}
};