摘樱桃 II 图解题解

摘樱桃 II 里两个机器人到底要干什么

给一张 rows 行 cols 列的网格 grid，坐标 (i,j)（行在前列在后，从 0 起）处有 grid[i][j] 颗樱桃。机器人 1 从 (0,0)、机器人 2 从 (0,cols−1) 出发走到最后一行，每步走下一行的左下、正下、右下之一，各收沿途樱桃，同格被两个同时踩到只算一次。求两条路合计最多收多少。

题面例子 grid=[[3,1,1],[2,5,1],[1,5,5],[2,1,1]] 答案 24。两条路互相牵制，没法分开各算。

两个机器人为什么不能各求各的最长路

让两个机器人各自求最长路再相加会错：同格只算一次把两条路绑死，各自最优常撞同一批高樱桃格，重合被算两遍、虚高。枚举所有走法配对更不行：每个机器人近 3^(rows−1) 条路，配对是平方级，用 O(...)（大 O 记号，规模变大时运算量怎么涨）记就是指数，跑不完。

状态为什么必须同时装下两个机器人的列

两机器人每步都往下移一行，所以两个永远停在同一行——正因如此，状态才只需装下两列 (c1,c2)、行号不进状态。局面只差各在哪列。用动态规划，状态 dp[c1][c2] 指两机器人分别在第 c1、c2 列时的最大樱桃。状态只两列，数为 cols²、非 cols。初始只有 dp[0][cols−1] = grid[0][0] + grid[0][cols−1]（cols 为 1 时同格只加一次）。

每步 9 种落点怎么转移，同格为什么只加一次

从局面 dp[c1][c2] 往下一行，两机器人各三方向（左下/正下/右下）、3×3=9 种落点，越界的丢掉。落点在第 nc1、nc2 列，收益 gain = grid[r][nc1]，nc1 ≠ nc2 时再加 grid[r][nc2]，同格 nc1 == nc2 只加一份。转移让 ndp[nc1][nc2] 取原值与 dp[c1][c2] + gain 的较大值；一行算完把 dp 换成 ndp 再往下。

拿题面 4 行 3 列，dp 怎么一行行填到 24

第 0 行 dp[0][2] = 3 + 1 = 4。第 1 行从 (0,2) 出发，机器人 1 落第 0 列收 2、机器人 2 落第 1 列收 5，共 7，dp[0][1] = 4 + 7 = 11。第 2 行两机器人各右移一列，收本行 5 和 5，dp[1][2] = 11 + 10 = 21。第 3 行各左移一列收 2 和 1，dp[0][1] = 21 + 3 = 24，扫末行取最大即 24。注意 dp[0][1] 第 1 行是 11、第 3 行成 24：不同行的同名格，滚动数组逐行覆盖，不是矛盾。

同格那份樱桃多加一次，24 为什么会算成更大

复杂度：每行 cols² 个局面各枚举 9 方向、共 rows 行，时间 O(rows·cols²·9)；滚动数组只存当前行，空间 O(cols²)。

同格忘去重、nc1 == nc2 时仍加两份，dp 会虚高偏大。走不到的局面初值要设成很小的负数（代码里 -10^9），设成 0 会被当合法起点、凭空冒樱桃。单列 cols == 1 时初始化也别加两份。

Python

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)

C++

#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;
    }
};

Java

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;
    }
}