LeetCode 剑指 Offer 47. 礼物的最大价值

约 9 分钟
文章信息 9 个分类 3 个标签
分类
LeetCode CodeTop 中等 未解决 2-5 字节跳动 阿里巴巴 剑指 Offer 剑指 Offer（第 2 版）
标签
数组 动态规划 矩阵
目录

题目描述

✅ 剑指 Offer 47. 礼物的最大价值

image-20241107211613899

题意分析

在一个 m 行 n 列的棋盘上，每格有一个非负的礼物价值。从左上角出发，每步只能向右或向下走一格，走到右下角，求路径上能拿到的价值总和的最大值。

「只能向右或向下」这条约束非常强：它意味着路径不会绕圈，任何格子只可能从它的正上方或正左方进入，且行号列号都单调不减。这既保证了子问题之间没有环，也决定了递推可以按行从上到下、按列从左到右单向推进。

价值非负这一点也要留意：它让「不存在的方向」可以安全地按 0 处理，第一行和第一列因此不用单独初始化。若价值允许为负，0 就成了一个虚假的高值候选，必须改用负无穷。

边界包括：只有一行时答案是整行之和，只有一列时是整列之和；1×1 的棋盘直接返回那一个格子的值。

解法：一维动态规划

核心思路

最朴素的做法是枚举全部路径。从左上到右下要走 m+n-2 步，其中选 m-1 步向下，路径条数是组合数 $\binom{m+n-2}{m-1}$，规模爆炸。瓶颈在于大量路径共享相同的后半段，却被反复重算——同一个格子被不同前缀重复访问了无数次。

观察到「到达某个格子后，后面能拿多少与它是怎么来的无关」，也就是无后效性：只有「当前在哪个格子」和「已经攒了多少」有意义，路径的具体形状可以丢掉。于是把「到达某格的最大累计价值」定义成状态即可。

二维状态定义是 f[i][j] = 从左上角走到格子 (i, j) 时能获得的最大价值，转移为 f[i][j] = max(f[i-1][j], f[i][j-1]) + grid[i][j]，边界上不存在的方向按 0 计。

再观察依赖关系：f[i][j] 只用到上一行的同列和本行的前一列，一整张二维表里除了这两个值其余都是死数据。按行推进时用一维数组 dp 滚动即可——在处理第 i 行第 j 列的那一刻，dp[j] 还没被本行覆盖，存的是 f[i-1][j]（上方）；dp[j-1] 已经在本行被覆盖过，存的是 f[i][j-1]（左方）。这条「同一个数组里，未更新的是上一行、已更新的是本行」的性质，就是滚动数组要维护的不变量，它也强制了内层循环必须从左往右。

于是最终的状态定义落到一维：处理完第 i 行第 j 列后，dp[j] 表示走到格子 (i, j) 的最大价值。遍历结束时 dp[n-1] 就是走到右下角的答案。

解题步骤

  • 取出行数 m 和列数 n，开一个长度为 n 的数组 dp，全部初始化为 0。全 0 的初值同时承担了两件事：它代表「第 -1 行」这条不存在的上方边界，价值贡献为 0；也让第一行的转移自动退化成前缀和。
  • 外层按行遍历、内层按列从左往右遍历。行从上到下是因为转移依赖上一行；列从左到右是滚动数组不变量成立的前提，反过来遍历会让 dp[j-1] 变成上一行的值，含义错乱。
  • 每个格子先取 left：j 为 0 时置 0，否则取 dp[j-1]。置 0 而不是负无穷，是因为价值非负，max(0, up) 不会让第一列错误地选中一个不存在的方向。
  • 再取 up 为当前的 dp[j]，这一步必须在写回之前完成，否则上方的值就被覆盖丢失了。
  • 写回 dp[j] = max(left, up) + grid[i][j]，完成一次状态转移，此时 dp[j] 的含义从「上一行的 j 列」切换成「本行的 j 列」。
  • 全部遍历完返回 dp[n-1]，即走到最后一行最后一列的最大价值。

以 grid = [[1,3,1],[1,5,1],[4,2,1]] 走一遍，dp 初始为 [0,0,0]。

处理第 0 行。j = 0：left 置 0，up = dp[0] = 0，dp[0] = 0 + 1 = 1。j = 1：left = dp[0] = 1，up = dp[1] = 0，取 1，dp[1] = 1 + 3 = 4。j = 2：left = dp[1] = 4，up = 0，dp[2] = 4 + 1 = 5。此时 dp = [1,4,5]，正是第一行的前缀和，符合「第一行只能一路向右」的直觉。

处理第 1 行。j = 0：left 置 0，up = dp[0] = 1（上一行的值），dp[0] = 1 + 1 = 2，对应只能一路向下。j = 1：left = dp[0] = 2（已是本行的值），up = dp[1] = 4（仍是上一行的值），取 4，dp[1] = 4 + 5 = 9。这一步正好体现了不变量：同一个数组里 dp[0] 是本行、dp[1] 是上一行。j = 2：left = dp[1] = 9，up = dp[2] = 5，取 9，dp[2] = 9 + 1 = 10。dp = [2,9,10]。

处理第 2 行。j = 0：dp[0] = 2 + 4 = 6。j = 1：left = 6，up = 9，取 9，dp[1] = 9 + 2 = 11。j = 2：left = 11，up = 10，取 11，dp[2] = 11 + 1 = 12。

返回 dp[2] = 12，对应路径 1 → 3 → 5 → 2 → 1，与手算的最优路径一致。

代码实现

class Solution {
    public int maxValue(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int[] dp = new int[n];

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int left = 0;
                if (j > 0) {
                    left = dp[j - 1];
                }
                int up = dp[j];
                dp[j] = Math.max(left, up) + grid[i][j];
            }
        }

        return dp[n - 1];
    }
}

func maxValue(grid [][]int) int {
    m, n := len(grid), len(grid[0])
    dp := make([]int, n)

    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            left := 0
            if j > 0 {
                left = dp[j-1]
            }
            up := dp[j]
            if left > up {
                dp[j] = left + grid[i][j]
            } else {
                dp[j] = up + grid[i][j]
            }
        }
    }

    return dp[n-1]
}

复杂度分析

  • 时间复杂度：$O(m \cdot n)$，每个格子只被访问一次，每次转移是常数次比较和加法。
  • 空间复杂度：$O(n)$，只保留一行长度的滚动数组；若不做滚动优化则是 $O(m \cdot n)$，若允许原地修改 grid 则可以做到 $O(1)$ 额外空间。

关键点总结

  • 路径类计数或最值问题先验证无后效性：只要「后续收益只取决于当前位置而与来路无关」，就能把指数级的路径枚举压成多项式级的状态转移。
  • 状态定义必须写成一句完整的话（「走到 (i, j) 时的最大价值」），转移方程和边界初值都从这句话推导，而不是先写循环再凑公式。
  • 二维 DP 只依赖上一行和本行左侧时，滚动成一维是标准优化；配套的硬性要求是内层循环从左往右，靠「未更新即上一行、已更新即本行」这条不变量吃掉一个维度。
  • 用 0 表示不存在的方向只在取值非负时成立，一旦允许负值就要换成负无穷，否则虚假的 0 会污染最大值。
  • 面试视角：这题的标准答题路径是「二维 DP 讲清楚 → 指出依赖只有两格 → 滚动成一维」，主动完成这三步比直接甩出一维代码更能得分；面试官若追问能否 $O(1)$ 空间，答就地改写 grid，但要说明这会破坏输入，实际工程里需先确认调用方是否允许。

易错点总结

  • 错误写法：内层循环改成从右往左 for (int j = n - 1; j >= 0; j--) → 用例 [[1,3,1],[1,5,1],[4,2,1]]，dp[j-1] 取到的是上一行的值而非本行左邻，第二行算出的 dp 就已偏离，最终返回 9 而不是 12。
  • 错误写法：写回后再读 up，即 dp[j] = left + grid[i][j]; int up = dp[j]; → 上方的值在读之前就被覆盖，转移退化成「只能向右」，用例同上返回 1+3+1+1+1 = 7。
  • 错误写法：把 dp 数组放在行循环内部每行重新 new → 用例 [[1,2],[3,4]]，上一行的信息全部丢失，答案退化成最后一行的前缀和 3+4 = 7，正确答案是 1+3+4 = 8。
  • 错误写法：第一列的 left 取 dp[n-1] 或不特判直接 dp[j-1] → 用例 [[1,2],[3,4]]，j = 0 时 dp[-1] 在 Java 里直接数组越界异常，Go 里同样 panic。
  • 错误写法：把 left 的默认值写成 Integer.MIN_VALUE 后再 + grid[i][j] → 用例任意含第一列的输入，加法直接溢出成一个极大正数，答案完全错乱。
  • 错误写法：返回 dp[0] 或 Math.max 全数组 → 用例 [[1,100],[1,1]]，dp 最终是 [2,102]，返回 dp[0] 得 2；题目要求的是走到右下角，不是路径最优端点。
  • 错误写法：转移写成 dp[j] = max(left + grid[i][j], up) 把加法只挂在一边 → 用例 [[1,3,1],[1,5,1],[4,2,1]]，走上方向来时漏加了当前格的价值，返回 7 而不是 12。
  • 错误写法：用 n = grid.length 取列数 → 用例 [[1,2,3]]，m 和 n 都被当成 1，dp 长度为 1，只累加第一列，返回 1 而不是 6。
  • 错误写法：直接贪心，每步选右边和下边中较大的格子 → 用例 [[1,10,1],[1,1,1],[100,1,1]]，贪心第一步会走向 10，最终拿不到左下角的 100，返回 14，正确答案是 1+1+100+1+1 = 104。
  • 错误写法：认为答案是「行最大值之和」或类似的整行聚合 → 用例 [[1,100],[100,1]]，两行最大值相加得 200，但任何合法路径都拿不到两个 100，正确答案是 102。

相似题目

题目 难度 考察点
62. 不同路径 中等 转移从取最大值变成求和，统计路径条数而非最优值
63. 不同路径 II 中等 障碍格状态强制置 0，且首行首列遇障碍后要全部截断
64. 最小路径和 中等 目标改为最小化，不存在的方向不能再用 0 代替
120. 三角形最小路径和 中等 每行长度递增，滚动时需从右往左更新避免覆盖
174. 地下城游戏 困难 正向 DP 会失效，必须从右下角倒推所需的最小初始血量
688. 骑士在棋盘上的概率 中等 移动方向有八个且可回退，状态要加上步数这一维
931. 下降路径最小和 中等 上一行可选左上、正上、右上三个来源，起点终点都不固定
1289. 下降路径最小和 II 困难 要求相邻行不同列，需用上一行的最小值与次小值做 $O(n)$ 转移
1301. 最大得分的路径数目 困难 同时维护最大得分与达到该得分的方案数，两个 DP 并行推进
1594. 矩阵的最大非负积 中等 乘法下负负得正，必须同时维护每格的最大积与最小积
LCR 098. 不同路径 中等 62 的中文版，可用来对照组合数公式与 DP 两种解法
LCR 099. 最小路径和 中等 64 的中文版，适合练最小化时首行首列的显式初始化
LCR 100. 三角形最小路径和 中等 120 的中文版，推荐用自底向上写法省掉边界特判