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

发布时间:2024年01月08日

个人主页:元清加油_【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. 返回值

  • 状态显示
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];
    }
};

文章来源:https://blog.csdn.net/weixin_74268082/article/details/135454500
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。