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 可以拿到最高价值的珠宝

算法原理讲解

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

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

• 状态显示

• 状态转移方程

• 从 [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]

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

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

• 填表顺序

• 返回值

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