【动态规划】LeetCode-LCR166.珠宝的最高价值

🎈算法那些事专栏说明：这是一个记录刷题日常的专栏，每个文章标题前都会写明这道题使用的算法。专栏每日计划至少更新1道题目，在这立下Flag🚩
🏠个人主页：Jammingpro
📕专栏链接：算法那些事
🎯每日学习一点点，技术累计看得见

题目

题目描述

现有一个记作二维矩阵 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

题解

由题目可知，我们只能向下走或者向右走。若我们走到第i行第j列，则我们的上一步一定是第i行第j-1列向右走1步到达的，或者是从第i-1行第j列向下走1步到达的。因而，我们想知道到达第i行第j列的最大价值，就需要知道到达第i行第j-1列、第i-1行第j列的最大价值。

首先，我们可以创建1个dp表（二维数组），用于保存到达第i行第j列的最大价值。第0行初始化规则为dp[0][0]=frame[0][0]，余下元素初始化规则为dp[0][i]=dp[0][i-1]+frame[0][i]。因为只能从第0行第i-1列向右走1步到达，而不能从第-1行第i列向下走1步到达（这样就超出frame范围了，不满足题意）。第0列初始化规则为dp[0][0]=frame[0][0]，余下元素初始化规则为dp[i][0]=dp[i-1][0]+frame[i][0]。因为只能从第i-1行第0列向下走1步到达。到此为止，我们得到了如下的dp表↓↓↓
在这里插入图片描述
余下的各行各列元素，均可由上面一个元素向下走1步到达，也可以由左边元素向右走1步到达。即dp[i][j]=max(dp[i-1][j],dp[i][j-1])+frame[i][j]。因为我们在计算第i行第j列元素时，必须先知道到达第i-1行第j-1列的最大价值，因此需要从左上向右下遍历。上述分析，以示例1执行示意图如下↓↓↓
在这里插入图片描述
经过上面的分析，我们可以得到如下代码↓↓↓

class Solution {
public:
    int jewelleryValue(vector<vector<int>>& frame) {
        int m = frame.size();
        int n = frame[0].size();
        vector<vector<int>>dp(m, vector<int>(n));
        dp[0][0] = frame[0][0];
        //初始化第0列
        for(int i = 1; i < m ;i++)
            dp[i][0] = dp[i - 1][0] + frame[i][0];
        //初始化第0行
        for(int i = 1; i < n; i++)
            dp[0][i] = dp[0][i - 1] + frame[0][i];
        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][j];
        return dp[m - 1][n - 1];
    }
};

我们可以通过多开辟1行1列，并将多开辟的1行1列初始化为0的方式，避开初始化第0行第0列的代码，这样可以使代码更加简洁。下面代码的思路与上述代码一致。↓↓↓

class Solution {
public:
    int jewelleryValue(vector<vector<int>>& frame) {
        int m = frame.size();
        int 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];
    }
};