摘樱桃 II 图解题解

这道题到底在问什么

输入

grid=[[3,1,1],[2,5,1],[1,5,5],[2,1,1]]

输出

24

先想最直接的笨办法

记住三件事:状态是「两机器人的列对 (c1,c2)」、每行枚举 9 种落点组合取最大、两机器人同格时樱桃只加一次。下面逐帧套它。（动画第 3 步）

最优解：一步一步想明白

1. 3记住三件事:状态是「两机器人的列对 (c1,c2)」、每行枚举 9 种落点组合取最大、两机器人同格时樱桃只加一次。下面逐帧套它。
2. 4这是 4 行 3 列的樱桃网格。机器人 1 在左上角 (0,0)、机器人 2 在右上角 (0,2);它们要同步逐行下移直到最后一行。下面把每一行的「两机器人列对」状态 dp 都算出来。
3. 5机器人 1 站在 (0,0) 收 3 颗(紫),机器人 2 站在 (0,2) 收 1 颗(青)。它们分列两端、不同格,所以 dp[0][2] = 3 + 1 = 4,其余状态暂时都是「走不到」。
4. 6两机器人在第 0 行,沿最优来到列对 (0,2),此时累计 4 颗。要往第 1 行走:各自先按左下、正下、右下枚举 3 个方向(共 9 种方向组合),越界的丢掉。机器人 1 的界内落点是列 0、1(2 个),机器人 2 的界内落点是列 1、2(2 个),所以本行实际有效组合 4 种,逐一算收益取最大。
5. 7先看机器人 1:它在第 0 行的列 0(蓝),下一行能落到列 0 或 1(界内的方向,橙色高亮)。这些落点脚下分别能拿 2、5 颗樱桃。机器人 2 的来源格(列 2)也标成蓝,但它不是机器人 1 的落点。
6. 8再看机器人 2:它在第 0 行的列 2(蓝),下一行能落到列 1 或 2(橙色高亮),脚下分别能拿 5、1 颗樱桃。机器人 1 的两个候选与机器人 2 的两个候选两两配对,就是要比较的 4 种落点组合。
7. 9其中最优的一组落点是列对 (0,1)。机器人 1 落 (1,0) 收 2,机器人 2 落 (1,1) 收 5,不同格、各算,本行收益 = 2 + 5 = 7。
8. 10反例:若两机器人都挤到同一列 1,樱桃 5 只算一次,本行只收 5 颗,明显比分开落点的 7 颗少。所以仍按 9 个方向组合枚举、越界的跳过,界内有效的都要比一遍、取最大,绝不能让它们随便重合。
9. 11dp[0][1] = 上一行 dp[0][2](4) + 本行收益 = 11。这是走到第 1 行、列对 (0,1) 能攒到的最多樱桃(蓝=已走定)。继续下一行。
10. 12两机器人在第 1 行,沿最优来到列对 (0,1),此时累计 11 颗。要往第 2 行走:各自先按左下、正下、右下枚举 3 个方向(共 9 种方向组合),越界的丢掉。机器人 1 的界内落点是列 0、1(2 个),机器人 2 的界内落点是列 0、1、2(3 个),所以本行实际有效组合 6 种,逐一算收益取最大。
11. 13先看机器人 1:它在第 1 行的列 0(蓝),下一行能落到列 0 或 1(界内的方向,橙色高亮)。这些落点脚下分别能拿 1、5 颗樱桃。机器人 2 的来源格(列 1)也标成蓝,但它不是机器人 1 的落点。
12. 14再看机器人 2:它在第 1 行的列 1(蓝),下一行能落到列 0 或 1 或 2(橙色高亮),脚下分别能拿 1、5、5 颗樱桃。机器人 1 的两个候选与机器人 2 的三个候选两两配对,就是要比较的 6 种落点组合。
13. 15其中最优的一组落点是列对 (1,2)。机器人 1 落 (2,1) 收 5,机器人 2 落 (2,2) 收 5,不同格、各算,本行收益 = 5 + 5 = 10。
14. 16dp[1][2] = 上一行 dp[0][1](11) + 本行收益 = 21。这是走到第 2 行、列对 (1,2) 能攒到的最多樱桃(蓝=已走定)。继续下一行。
15. 17两机器人在第 2 行,沿最优来到列对 (1,2),此时累计 21 颗。要往第 3 行走:各自先按左下、正下、右下枚举 3 个方向(共 9 种方向组合),越界的丢掉。机器人 1 的界内落点是列 0、1、2(3 个),机器人 2 的界内落点是列 1、2(2 个),所以本行实际有效组合 6 种,逐一算收益取最大。
16. 18先看机器人 1:它在第 2 行的列 1(蓝),下一行能落到列 0 或 1 或 2(界内的方向,橙色高亮)。这些落点脚下分别能拿 2、1、1 颗樱桃。机器人 2 的来源格(列 2)也标成蓝,但它不是机器人 1 的落点。
17. 19再看机器人 2:它在第 2 行的列 2(蓝),下一行能落到列 1 或 2(橙色高亮),脚下分别能拿 1、1 颗樱桃。机器人 1 的三个候选与机器人 2 的两个候选两两配对,就是要比较的 6 种落点组合。
18. 20其中最优的一组落点是列对 (0,1)。机器人 1 落 (3,0) 收 2,机器人 2 落 (3,1) 收 1,不同格、各算,本行收益 = 2 + 1 = 3。
19. 21dp[0][1] = 上一行 dp[1][2](21) + 本行收益 = 24。这是走到第 3 行、列对 (0,1) 能攒到的最多樱桃(蓝=已走定)。到这里已经到达最后一行,下一步扫最后一行所有 dp 取最大。
20. 22走到最后一行,扫一遍所有 dp[c1][c2] 取最大,得到 dp[0][1] = 24,就是两机器人合计能收的最多樱桃。
21. 23绿色就是两机器人各自的最优路线。机器人 1:(0,0)→(1,0)→(2,1)→(3,0);机器人 2:(0,2)→(1,1)→(2,2)→(3,1)。一路收集、同格只算一次,合计 24 颗。这就是答案。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from typing import List
class Solution:
    def cherryPickup(self, grid: List[List[int]]) -> int:
        rows, cols = len(grid), len(grid[0])
        dp = [[-10**9] * cols for _ in range(cols)]
        dp[0][cols - 1] = grid[0][0] + (grid[0][cols - 1] if cols > 1 else 0)
        for r in range(1, rows):
            ndp = [[-10**9] * cols for _ in range(cols)]
            for c1 in range(cols):
                for c2 in range(cols):
                    if dp[c1][c2] < 0:
                        continue
                    for d1 in (-1, 0, 1):
                        for d2 in (-1, 0, 1):
                            nc1, nc2 = c1 + d1, c2 + d2
                            if 0 <= nc1 < cols and 0 <= nc2 < cols:
                                gain = grid[r][nc1] + (grid[r][nc2] if nc1 != nc2 else 0)
                                ndp[nc1][nc2] = max(ndp[nc1][nc2], dp[c1][c2] + gain)
            dp = ndp
        return max(max(row) for row in dp)

#include <vector>
using namespace std;
class Solution {
public:
    int cherryPickup(vector<vector<int>>& grid) {
        int R = grid.size(), C = grid[0].size();
        vector<vector<int>> dp(C, vector<int>(C, -1000000000));
        dp[0][C-1] = grid[0][0] + (C > 1 ? grid[0][C-1] : 0);
        for (int r = 1; r < R; ++r) {
            vector<vector<int>> ndp(C, vector<int>(C, -1000000000));
            for (int c1 = 0; c1 < C; ++c1) for (int c2 = 0; c2 < C; ++c2) if (dp[c1][c2] >= 0) {
                for (int d1 = -1; d1 <= 1; ++d1) for (int d2 = -1; d2 <= 1; ++d2) {
                    int nc1 = c1 + d1, nc2 = c2 + d2;
                    if (nc1 >= 0 && nc1 < C && nc2 >= 0 && nc2 < C) {
                        int gain = grid[r][nc1] + (nc1 == nc2 ? 0 : grid[r][nc2]);
                        ndp[nc1][nc2] = max(ndp[nc1][nc2], dp[c1][c2] + gain);
                    }
                }
            }
            dp.swap(ndp);
        }
        int ans = 0;
        for (auto &row : dp) for (int x : row) ans = max(ans, x);
        return ans;
    }
};

import java.util.*;
class Solution {
    public int cherryPickup(int[][] grid) {
        int R = grid.length, C = grid[0].length;
        int[][] dp = new int[C][C];
        for (int[] row : dp) Arrays.fill(row, -1_000_000_000);
        dp[0][C - 1] = grid[0][0] + (C > 1 ? grid[0][C - 1] : 0);
        for (int r = 1; r < R; r++) {
            int[][] ndp = new int[C][C];
            for (int[] row : ndp) Arrays.fill(row, -1_000_000_000);
            for (int c1 = 0; c1 < C; c1++) for (int c2 = 0; c2 < C; c2++) if (dp[c1][c2] >= 0) {
                for (int d1 = -1; d1 <= 1; d1++) for (int d2 = -1; d2 <= 1; d2++) {
                    int nc1 = c1 + d1, nc2 = c2 + d2;
                    if (nc1 >= 0 && nc1 < C && nc2 >= 0 && nc2 < C) {
                        int gain = grid[r][nc1] + (nc1 == nc2 ? 0 : grid[r][nc2]);
                        ndp[nc1][nc2] = Math.max(ndp[nc1][nc2], dp[c1][c2] + gain);
                    }
                }
            }
            dp = ndp;
        }
        int ans = 0;
        for (int[] row : dp) for (int x : row) ans = Math.max(ans, x);
        return ans;
    }
}

复杂度

面试官可能追问