LeetCode 741. 摘樱桃

2022-08-17 HGNULB 约 18 分钟

文章信息 6 个分类 3 个标签

分类

题目描述

✅ 741. 摘樱桃

题意分析

给定一个 $n \times n$ 的网格，格子取值只有三种：0 表示空地、1 表示有一颗樱桃、-1 表示荆棘（不可通行）。要从左上角 $(0,0)$ 出发、只能向右或向下走到右下角 $(n-1,n-1)$，再从右下角出发、只能向左或向上走回 $(0,0)$，返回两趟总共能摘到的最多樱桃数。樱桃摘走后格子变为 0，同一颗樱桃不会被摘两次。如果不存在合法往返路径，返回 0。

「摘走后变 0」是这道题的全部难点所在。如果两趟互不影响，答案就是「单趟最大值」乘二，而单趟最大值是一道入门级路径 DP。正因为有这条规则，两条路径产生了耦合：第二趟的收益依赖第一趟走过哪些格子，而第一趟的最优选择又要考虑给第二趟留下什么。这直接判了贪心的死刑——先求一条最优路径、把它清零、再在残图上求第二条最优路径，得到的往往不是全局最优。

第二个要读准的点：返程只能向左或向上。这意味着返程路径反过来看，就是一条从 $(0,0)$ 到 $(n-1,n-1)$ 的、只能向右或向下的路径。所以「去 + 回」在结构上完全对称，两趟是同一类对象。这个观察是把问题变成可解形式的钥匙。

第三，「不存在合法路径返回 0」要求实现能区分「走通了但一颗樱桃都没摘到」和「根本走不通」。前者答案是 0，后者答案也是 0，看似不用区分；但在 DP 内部必须区分，否则「不可达」的状态会被当成「收益为 0 的可达状态」参与转移，把荆棘穿透过去。

约束是 $1 \le n \le 50$。$n^3$ 是 $1.25 \times 10^5$，$n^4$ 是 $6 \times 10^6$，都能过；但 $n^4$ 的状态数（两个人各自的二维坐标）里有大量非法组合，题目给这个规模，是在允许你用一个三维状态从容地做。

解法：三维 DP（按步数滚动）

核心思路

先说为什么贪心不行。以一个中间只有一条窄通道的网格为例，第一趟贪心地吃光通道上的樱桃后，第二趟被迫走一条几乎没有收益的路；而如果第一趟稍微让一让、走一条次优路线，两趟合计反而更多。局部最优不导出全局最优，两趟必须同时决策。

「同时决策」怎么落地？借助上面那个观察：把返程反向，它就是第二条从 $(0,0)$ 到 $(n-1,n-1)$ 的下右路径。于是原问题等价于：两个人从 $(0,0)$ 同时出发、各自沿下右方向走到 $(n-1,n-1)$，求两人合计能摘到的最多樱桃，其中同时踩到的格子只算一次。 注意这个等价是严格的——两条下右路径的任意组合，都能还原成一条去程加一条回程，反之亦然，樱桃的重复计算规则也一一对应。

现在的问题是状态怎么设计。直觉上要记录两个人各自的坐标，那是四维 $(r_1, c_1, r_2, c_2)$。但这里有一个关键约束可以砍掉一维：两人的移动是同步的，走了 $t$ 步之后，一定有 $r + c = t$。因为每一步要么行加一、要么列加一，行列之和恰好等于步数。所以只要知道步数 $t$ 和行号 $r$，列号就唯一确定为 $c = t - r$。四维立刻降到三维。

于是显式写下状态定义：$dp[t][r_1][r_2]$ 表示两人各走了 $t$ 步、第一人位于 $(r_1,\ t - r_1)$、第二人位于 $(r_2,\ t - r_2)$ 时，合计能摘到的最大樱桃数；若该状态不可达，取负无穷。

转移来自上一步。第 $t$ 步的两人，各自可能是从上方（行号减一）或左方（行号不变）走来的，组合起来是 4 种前驱：$(r_1, r_2)$、$(r_1-1, r_2)$、$(r_1, r_2-1)$、$(r_1-1, r_2-1)$，全部取自 $dp[t-1]$。取这 4 个中的最大值作为基底，再加上本步新摘到的樱桃：

本步收益 $= grid[r_1][c_1]$，若 $r_1 \ne r_2$ 则再加 $grid[r_2][c_2]$。为什么用 $r_1 \ne r_2$ 判断「是否同格」而不比较完整坐标：同一步数下列号由行号唯一决定，行号相同就意味着坐标完全相同，一个比较足矣。这是「$r + c = t$」这条不变量顺带送的便利。

不可达的表示必须用负无穷而不是 0。理由有二：其一，荆棘格永远不能被踩，凡是 $grid[r][c] = -1$ 的状态直接跳过，不产生任何值；其二，如果 4 个前驱全是负无穷，说明当前状态没有任何合法来路，它自己也必须保持负无穷，不能因为「本步能摘 1 颗」就变成 1。代码里用 best != negInf 这个判断守住了这条底线。负无穷的具体取值要留足余量（Java 里用 Integer.MIN_VALUE / 4），避免加法把它撞成正数。

步数从 0 到 $2(n-1)$，$dp[t]$ 只依赖 $dp[t-1]$，所以第一维可以滚动掉，只保留两个 $n \times n$ 的二维表。行号的合法范围也可以提前收紧：$c = t - r$ 要落在 $[0, n-1]$ 内，等价于 $r \in [\max(0,\ t - (n-1)),\ \min(n-1,\ t)]$，按这个范围枚举能省掉大量无效格子。

最后，答案是 $dp[2(n-1)][n-1][n-1]$，即两人都到达右下角的状态。若它仍是负无穷（说明荆棘把路彻底堵死），按题意返回 0，所以取 $\max(0, \cdot)$。

解题步骤

第一步，把 $dp$ 全部初始化为负无穷，再令 $dp[0][0] = grid[0][0]$。 为什么起点只加一次 $grid[0][0]$：两人都站在 $(0,0)$，属于同格情形，樱桃只算一次。为什么其余全是负无穷：$t = 0$ 时两人只可能都在起点，别的行号组合根本不存在。若起点是荆棘，$grid[0][0] = -1$，这个 -1 会在后续转移中被 grid[r1][c1] == -1 的检查拦住，最终答案仍为 0。

第二步，按 $t$ 从 1 递增到 $2(n-1)$，每轮新建一张全负无穷的 $ndp$。 为什么必须新建而不是原地更新：$dp[t]$ 的 4 个前驱全部来自 $dp[t-1]$，原地写会让同一轮内已更新的格子污染后续转移。滚动数组省的是第一维的空间，不是新旧两张表的区分。

第三步，计算本轮合法行号区间 $[\max(0, t-(n-1)),\ \min(n-1, t)]$，双重循环枚举 $r_1$、$r_2$。 为什么要先收紧范围：$t$ 较大时小行号对应的列号会超出右边界，$t$ 较小时大行号对应的列号会是负数，提前收紧比在循环里逐个判断更清晰，也避免了下标为负导致的越界。

第四步，由 $c_1 = t - r_1$、$c_2 = t - r_2$ 还原列号，若任一格越界或为荆棘就跳过。 为什么荆棘要跳过而不是记 0：荆棘不可通行，站在上面的状态根本不存在，必须保持负无穷，否则路径会从荆棘上穿过去。

第五步，算本步收益：先取 $grid[r_1][c_1]$，若 $r_1 \ne r_2$ 再加 $grid[r_2][c_2]$。 为什么同格时只加一次：题目规定樱桃摘走后变 0，两人同时到达时只能收获一份。

第六步，遍历 4 种前驱组合取最大值 $best$，跳过行号为负的非法前驱。 为什么是 4 种：每个人独立地有「从上来」和「从左来」两种可能，二者组合即 $2 \times 2$。为什么两人的选择相互独立：他们各自走各自的路，唯一的耦合是同格时樱桃只算一次，而这已经在本步收益里处理过了。

第七步，仅当 $best$ 不是负无穷时，才令 $ndp[r_1][r_2] = best + $ 本步收益。 为什么要这个守卫：没有任何合法前驱就意味着当前状态不可达，直接赋值会把负无穷加上一个小正数，得到一个仍然很负但已被污染的值；更糟的是若负无穷取值不够小，可能被后续累加抬成正数，凭空造出不存在的路径。

第八步，一轮结束后令 $dp = ndp$，进入下一步数。

第九步，返回 $\max(0,\ dp[n-1][n-1])$。 为什么要和 0 取最大：不可达时该状态是负无穷，题意要求此时返回 0。

以 grid = [[0,1,-1],[1,0,-1],[1,1,1]]（$n = 3$）走一遍，网格三行依次是 0 1 -1、1 0 -1、1 1 1。

$t = 0$：$dp[0][0] = grid[0][0] = 0$，其余负无穷。

$t = 1$：行号范围 $[\max(0,-1),\ \min(2,1)] = [0, 1]$。
$(r_1,r_2) = (0,0)$：两人都在 $(0,1)$，$grid = 1$，同格只算一次，收益 1。唯一合法前驱是 $dp[0][0] = 0$，得 $ndp[0][0] = 1$。
$(0,1)$：第一人在 $(0,1)$ 值 1，第二人在 $(1,0)$ 值 1，行号不同，收益 2。前驱中 $dp[0][0] = 0$ 可用，得 3 中最大的基底 0，$ndp[0][1] = 2$。
$(1,0)$：对称，$ndp[1][0] = 2$。
$(1,1)$：两人都在 $(1,0)$，收益 1，前驱只有 $dp[0][0] = 0$，$ndp[1][1] = 1$。

$t = 2$：行号范围 $[0, 2]$。但 $r = 0$ 对应列号 2，$grid[0][2] = -1$ 是荆棘，所有含 $r_1 = 0$ 或 $r_2 = 0$ 的组合全被跳过——荆棘在这里第一次发挥了剪枝作用。
$(1,1)$：两人都在 $(1,1)$ 值 0，收益 0。4 个前驱 $dp[1][1] = 1$、$dp[1][0] = 2$、$dp[0][1] = 2$、$dp[0][0] = 1$，最大 2，$ndp[1][1] = 2$。
$(1,2)$：第一人在 $(1,1)$ 值 0，第二人在 $(2,0)$ 值 1，收益 1。前驱中 $dp[1][2]$ 与 $dp[0][2]$ 在上一轮不存在（负无穷），可用的是 $dp[1][1] = 1$ 与 $dp[0][1] = 2$，最大 2，$ndp[1][2] = 3$。
$(2,1)$：对称，$ndp[2][1] = 3$。
$(2,2)$：两人都在 $(2,0)$ 值 1，收益 1。前驱仅 $dp[1][1] = 1$ 可用，$ndp[2][2] = 2$。

$t = 3$：行号范围 $[\max(0,1),\ \min(2,3)] = [1, 2]$。$r = 1$ 对应列号 2，$grid[1][2] = -1$ 是荆棘，跳过。
$(2,2)$：两人都在 $(2,1)$ 值 1，收益 1。前驱 $dp[2][2] = 2$、$dp[2][1] = 3$、$dp[1][2] = 3$、$dp[1][1] = 2$，最大 3，$ndp[2][2] = 4$。这一步是全题最能说明「两人独立选前驱」的地方：基底 3 来自 $(2,1)$ 或 $(1,2)$，也就是上一轮两人分处不同格子的状态。

$t = 4$：行号范围 $[2, 2]$，只有 $(2,2)$。两人都在 $(2,2)$ 值 1，收益 1。前驱中只有 $dp[2][2] = 4$ 可用（$dp[2][1]$、$dp[1][2]$、$dp[1][1]$ 在上一轮都是负无穷），$ndp[2][2] = 5$。

返回 $\max(0, 5) = 5$。还原成实际路径：一人走 $(0,0) \to (0,1) \to (1,1) \to (2,1) \to (2,2)$ 摘到 $0+1+0+1+1 = 3$，另一人走 $(0,0) \to (1,0) \to (2,0) \to (2,1) \to (2,2)$，其中 $(2,1)$、$(2,2)$ 与前者重合已被计过，独立贡献 $1 + 1 = 2$，合计 5。

顺带看一个不可达的例子：grid = [[1,1,-1],[1,-1,1],[-1,1,1]]。$t = 2$ 时行号范围是 $[0,2]$，但 $(0,2)$、$(1,1)$、$(2,0)$ 三个格子分别是 -1、-1、-1，全部被跳过，$ndp$ 整张表保持负无穷；此后每一轮的 $best$ 都是负无穷，守卫条件永不成立，最终 $dp[2][2]$ 仍是负无穷，返回 0。这正是「必须用负无穷而非 0 表示不可达」的价值——若用 0，第 3 步就会从一张全 0 的表继续累加，穿过荆棘算出一个正数。

代码实现

class Solution {
    public int cherryPickup(int[][] grid) {
        int n = grid.length;
        int negInf = Integer.MIN_VALUE / 4;

        int[][] dp = new int[n][n];
        for (int[] row : dp) {
            Arrays.fill(row, negInf);
        }
        dp[0][0] = grid[0][0];

        for (int t = 1; t <= 2 * (n - 1); t++) {
            int[][] ndp = new int[n][n];
            for (int[] row : ndp) {
                Arrays.fill(row, negInf);
            }

            int rMin = Math.max(0, t - (n - 1));
            int rMax = Math.min(n - 1, t);

            for (int r1 = rMin; r1 <= rMax; r1++) {
                for (int r2 = rMin; r2 <= rMax; r2++) {
                    int c1 = t - r1;
                    int c2 = t - r2;
                    if (c1 < 0 || c1 >= n || c2 < 0 || c2 >= n) {
                        continue;
                    }
                    if (grid[r1][c1] == -1 || grid[r2][c2] == -1) {
                        continue;
                    }

                    int cherries = grid[r1][c1];
                    if (r1 != r2) {
                        cherries += grid[r2][c2];
                    }

                    int best = negInf;
                    for (int dr1 = 0; dr1 <= 1; dr1++) {
                        for (int dr2 = 0; dr2 <= 1; dr2++) {
                            int pr1 = r1 - dr1;
                            int pr2 = r2 - dr2;
                            if (pr1 < 0 || pr2 < 0) {
                                continue;
                            }
                            best = Math.max(best, dp[pr1][pr2]);
                        }
                    }

                    if (best != negInf) {
                        ndp[r1][r2] = Math.max(ndp[r1][r2], best + cherries);
                    }
                }
            }

            dp = ndp;
        }

        return Math.max(0, dp[n - 1][n - 1]);
    }
}

func cherryPickup(grid [][]int) int {
    n := len(grid)
    const negInf = -1 << 60

    dp := make([][]int, n)
    for i := range dp {
        dp[i] = make([]int, n)
        for j := range dp[i] {
            dp[i][j] = negInf
        }
    }
    dp[0][0] = grid[0][0]

    for t := 1; t <= 2*(n-1); t++ {
        ndp := make([][]int, n)
        for i := range ndp {
            ndp[i] = make([]int, n)
            for j := range ndp[i] {
                ndp[i][j] = negInf
            }
        }

        rMin := max741(0, t-(n-1))
        rMax := min741(t, n-1)

        for r1 := rMin; r1 <= rMax; r1++ {
            for r2 := rMin; r2 <= rMax; r2++ {
                c1 := t - r1
                c2 := t - r2

                if c1 >= n || c2 >= n || grid[r1][c1] == -1 || grid[r2][c2] == -1 {
                    continue
                }

                cherries := grid[r1][c1]
                if r1 != r2 {
                    cherries += grid[r2][c2]
                }

                best := negInf
                for _, dr1 := range []int{0, 1} {
                    for _, dr2 := range []int{0, 1} {
                        pr1, pr2 := r1-dr1, r2-dr2
                        if pr1 >= 0 && pr2 >= 0 && dp[pr1][pr2] != negInf {
                            if dp[pr1][pr2] > best {
                                best = dp[pr1][pr2]
                            }
                        }
                    }
                }

                if best != negInf && best+cherries > ndp[r1][r2] {
                    ndp[r1][r2] = best + cherries
                }
            }
        }
        dp = ndp
    }

    if dp[n-1][n-1] < 0 {
        return 0
    }
    return dp[n-1][n-1]
}

func max741(a, b int) int {
    if a > b {
        return a
    }
    return b
}

func min741(a, b int) int {
    if a < b {
        return a
    }
    return b
}

复杂度分析

时间复杂度：$O(n^3)$。步数 $t$ 的取值有 $2n-1$ 个，每个步数下枚举 $(r_1, r_2)$ 是 $O(n^2)$，每个状态的转移固定检查 4 个前驱，是常数。$n \le 50$ 时约 $99 \times 2500 \times 4 \approx 10^6$ 次基本操作。注意每轮还要花 $O(n^2)$ 初始化 $ndp$，这与主循环同阶，不影响结论。

空间复杂度：$O(n^2)$。滚动掉步数维后只保留新旧两张 $n \times n$ 的表。若不滚动，三维表是 $O(n^3)$，$n = 50$ 时约 25 万个整数，其实也能承受，但滚动写法在这里几乎没有额外代价，没有理由不做。

关键点总结

两趟耦合的路径问题，要转成两条同时行走的路径。「摘完变 0」制造了两趟之间的依赖，使得分两次求最优必然失效。把返程反向、让两个人同步前进，是把顺序依赖改造成并行决策的标准手法，可以直接迁移到所有「往返取物」「双机器人收集」类题目。

同步移动带来的 $r + c = t$ 是降维的关键。凡是「每步恰好让某个量增加 1」的移动模型，行列之和就是一个可以充当时间轴的守恒量。抓住这类不变量，能把两人的四维坐标压成三维，进而滚动成二维。遇到多智能体网格题，先问一句「有没有守恒量能替代一维」。

不可达必须用负无穷显式表示，且要有 best != negInf 的守卫。用 0 表示不可达是这类题最隐蔽的坑：0 是一个合法的收益值，混用会让算法穿过障碍物。负无穷的量级还要留足余量，防止累加后翻正。

判重只需比较一个维度。因为列号由行号和步数唯一确定，r1 != r2 就等价于「不在同一格」。这种「靠不变量把多条件判断压成单条件」的简化，既提速也减少出错面。

滚动数组要新建而非原地更新。当转移同时引用上一层的多个位置时，原地写会让本层的新值污染尚未使用的旧值。判断标准很简单：转移式里出现的下标若在本层已被改写过，就必须分离新旧两张表。

面试视角：这题的考点不是写代码，而是能否在白板上讲出「为什么贪心两次不对」和「为什么可以把返程反向」。开口先给一个贪心失败的反例，再抛出双人同行的等价转换，接着报出状态定义 $dp[t][r_1][r_2]$ 并解释 $c = t - r$，最后说明负无穷的必要性——这四步讲完，代码本身反而是水到渠成的。若面试官追问变体，要能立刻指出 1463 题（两个机器人从顶行两侧同时向下走）是本题的简化版：因为两人步数天然同步且只走一个方向，状态直接是 $dp[row][c_1][c_2]$，不需要反向转换这一步。

易错点总结

错误写法：先求单趟最大路径，清零后在残图上再求一次，两次相加。以一个 $3 \times 3$ 网格 [[1,1,1],[0,0,1],[0,0,1]] 为例，第一趟贪心走完右列摘到 5 颗后全部清零，第二趟只能摘到 0，合计 5；但让两条路各走一侧其实也是 5，而在稍复杂的网格（如中间有窄通道）上贪心会明显低于最优。两条路径必须同时决策。

错误写法：用 0 而不是负无穷表示不可达状态。以 grid = [[1,1,-1],[1,-1,1],[-1,1,1]] 为例，$t = 2$ 时所有格子都是荆棘，正确的表应全是负无穷；用 0 的话第 3 步会从 0 开始继续累加，最终返回一个正数（如 2），而正确答案是 0——路径实际上穿过了荆棘。

错误写法：省掉 best != negInf 的守卫，直接写 ndp[r1][r2] = best + cherries。以 grid = [[0,-1],[-1,0]] 为例，$t = 1$ 时两个格子都是荆棘被跳过，$t = 2$ 时 $(1,1)$ 的 4 个前驱全是负无穷，无守卫会得到「负无穷 + 0」，若负无穷取的是 Integer.MIN_VALUE 还会直接整数下溢变成大正数，返回一个巨大的错误值。

错误写法：负无穷取 Integer.MIN_VALUE。以任意 $n = 50$ 的网格为例，转移中会执行 负无穷 + cherries，最多累加 $2n$ 次，Integer.MIN_VALUE 加上正数虽不会立刻溢出，但一旦某处写成 负无穷 * 2 或与其它负值相加就会翻正。留出 4 倍余量（Integer.MIN_VALUE / 4）是标准做法。

错误写法：同格时也把两份樱桃都加上。以 grid = [[1,1],[1,1]] 为例，起点 $(0,0)$ 与终点 $(1,1)$ 两人必然同格，重复计数会得到 6，而正确答案是 4（四个格子每颗只能摘一次，两条路合起来最多覆盖全部四格）。

错误写法：用 r1 == r2 && c1 == c2 判同格，但 $c_1$、$c_2$ 算错。若把列号写成 $c = t + r$ 或 $c = r - t$，同格判断和越界判断会同时失效。以 $n = 2$、$t = 1$ 为例，正确的 $(r,c)$ 组合只有 $(0,1)$ 和 $(1,0)$，公式写错会取到 $(0,-1)$ 之类的非法坐标，Java 抛越界异常，Go 直接 panic。

错误写法：滚动时原地更新 $dp$ 而不新建 $ndp$。以 $n = 3$ 的任意网格为例，计算 $ndp[1][1]$ 时需要旧的 $dp[0][0]$，但若 $(0,0)$ 已在本轮被覆盖成第 $t$ 步的值，转移就跨了一步，结果偏大。表现为答案在某些用例上莫名超出理论上限。

错误写法：行号枚举范围直接用 $[0, n-1]$，靠越界判断兜底，但漏写了 c1 < 0 的检查。以 $n = 3$、$t = 1$、$r_1 = 2$ 为例，$c_1 = 1 - 2 = -1$，Java 访问 grid[2][-1] 抛 ArrayIndexOutOfBoundsException。要么收紧枚举范围，要么两侧越界都判。

错误写法：只考虑 2 种前驱（两人同向移动）而非 4 种。以 grid = [[0,1,-1],[1,0,-1],[1,1,1]] 为例，$t = 3$ 时最优基底 3 来自前驱 $(2,1)$ 或 $(1,2)$，即两人上一步分处不同行；只允许两人同时下移或同时右移会漏掉这些状态，最终返回 4 而非 5。

错误写法：步数循环写成 t <= 2*n 或 t < 2*(n-1)。前者会让 $t$ 超出可达范围，行号区间为空、$ndp$ 全是负无穷，最终返回 0；后者少走一步，$dp[n-1][n-1]$ 停在倒数第二步的值，以 grid = [[1,1],[1,1]] 为例会返回 3 而不是 4。

错误写法：忘记对最终结果取 $\max(0, \cdot)$。以 grid = [[1,-1],[-1,1]] 为例，两条对角线都被荆棘隔断，$dp[1][1]$ 保持负无穷，直接返回会输出一个极大的负数，而题目要求返回 0。

错误写法：起点初始化写成 dp[0][0] = 2 * grid[0][0]。以 grid = [[1]] 为例，$n = 1$ 时循环一次都不进，直接返回 2，而正确答案是 1——起点这一格的樱桃只能摘一次。

相似题目

题目	难度	考察点
64. 最小路径和	中等	单条下右路径求最小和，是本题剥掉「两趟耦合」后的骨架
63. 不同路径 II	中等	同样有障碍物且只能下右，但求方案数而非最值，障碍处置 0 而非负无穷
62. 不同路径	中等	无障碍的纯计数，可直接用组合数 $O(1)$ 求解
174. 地下城游戏	困难	同为网格 DP 但必须从终点倒推，因为约束是「过程中血量不得归零」而非终点最值
120. 三角形最小路径和	中等	状态退化为一维，自底向上滚动即可，重点在下标偏移
931. 下降路径最小和	中等	每行可斜向移动，前驱有 3 个而非 2 个，边界列要单独处理
980. 不同路径 III	困难	要求恰好走遍所有空格且可四向移动，状态无法压缩，只能回溯搜索
329. 矩阵中的最长递增路径	困难	移动方向不受限但受数值单调约束，需记忆化搜索而非按层递推