跳到主要内容

LCR 166.珠宝的最高价值

· 阅读需 3 分钟

1、题干​

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

 

2、解法1-动态规划​

循环遍历矩阵，累加礼物价值

状态转移方程：dp[i][j]+=max(dp[i−1][j],dp[i][j−1])dp[i][j] += max(dp[i-1][j], dp[i][j-1])


3、代码​

function maxValue(grid: number[][]): number {
    const m = grid.length, n = grid[0].length;
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            grid[i][j] += Math.max(i > 0 ? grid[i - 1][j] : 0, j > 0 ? grid[i][j - 1] : 0);
        }
    }
    return grid[m - 1][n - 1];
};

4、执行结果​

image.png


5、解法2-记忆化DFS​

DFS遍历矩阵，累加礼物价值

记录每个节点的最大价值作为缓存避免重复计算


6、代码​

function maxValue(grid: number[][]): number {
    const m = grid.length, n = grid[0].length;
    const visited = grid.map(row => row.map(() => 0));
    function dfs(i: number, j: number) {
        if (i < 0 || j < 0 || i >= m || j >= n) return 0;
        if (!visited[i][j]) visited[i][j] = grid[i][j] + Math.max(dfs(i - 1, j), dfs(i, j - 1));
        return visited[i][j];
    }
    return dfs(m - 1, n - 1);
};

7、执行结果​

  • 执行用时: 56 ms
  • 内存消耗: 44.1 MB