年薪八十多万的领导，每天的工作就是催20个外包兄弟通宵改 BUG，自己喝着咖啡刷手机“摘果子”。。

摘樱桃这道题，听起来像是个悠闲的农场游戏，实际上是个标准的动态规划（Dynamic Programming, DP）问题。而且它还有个难点：要让两个人（或者说一次往返）尽可能多地摘樱桃。

想象一下，你和你的小伙伴在一个N×N的网格里，每个格子上可能有樱桃，也可能是空地，甚至有障碍物（无法通行）。你们的任务是 从左上角(0,0)出发到右下角(N-1,N-1)，尽可能多地摘樱桃，然后再回到起点。
但问题是，既然要回去，那不如直接把这个问题换成：两个人同时从 (0,0) 出发，一起走到 (N-1,N-1)，在不撞上的情况下尽可能多地摘樱桃。 这样就不需要回程的操作了（毕竟程序员都懂，优化能少一步是一步）。

所以，这道题的本质是 双人路径动态规划 问题。

思路解析

1. 状态定义设 dp[r1][c1][r2][c2] 表示 A 走到 (r1, c1) 时，B 走到 (r2, c2) 时，能够摘到的最大樱桃数。
   但问题是，这个状态太大了，四个维度 O(N^4) 直接爆炸。我们观察到 r1+c1 == r2+c2，因为两个人每次都同时走一步，总步数是一样的。因此，我们可以优化成 dp[k][i][j]，表示总共走了 k 步，A 在 (i, k-i)，B 在 (j, k-j) 时的最大樱桃数。

2. 状态转移既然每次只能往右或者往下走，那 A 和 B 在 k 步时可能是从 k-1 步的四种可能情况来的：

   那么状态转移方程是：

   dp[k][i][j] = max(dp[k-1][i-1][j-1],  # A下 B下
                     dp[k-1][i-1][j],    # A下 B右
                     dp[k-1][i][j-1],    # A右 B下
                     dp[k-1][i][j])      # A右 B右
   

   当然，遇到障碍物的格子，直接跳过（即设为 -inf）。

• A 和 B 都是从左边来的（→, →）
• A 从左，B 从上（→, ↓）
• A 从上，B 从左（↓, →）
• A 和 B 都是从上面来的（↓, ↓）

if i == j:
    dp[k][i][j] += grid[i][k-i]
else:
    dp[k][i][j] += grid[i][k-i] + grid[j][k-j]

代码实现

def cherryPickup(grid):
    n = len(grid)
    dp = [[[-float('inf')] * n for _ in range(n)] for _ in range(2 * n - 1)]
        dp[0][0][0] = grid[0][0]
        for k in range(1, 2 * n - 1):  
        for i in range(max(0, k - (n - 1)), min(n, k + 1)):
            for j in range(max(0, k - (n - 1)), min(n, k + 1)):
                if grid[i][k - i] == -1 or grid[j][k - j] == -1:
                    continue  
                best = -float('inf')
                for pi in (i - 1, i):
                    for pj in (j - 1, j):
                        if 0 <= pi < n and 0 <= pj < n:
                            best = max(best, dp[k - 1][pi][pj])
                if best < 0:
                    continue
                                dp[k][i][j] = best + grid[i][k - i]  
                if i != j:
                    dp[k][i][j] += grid[j][k - j]  
    return max(0, dp[2 * n - 2][n - 1][n - 1])

为什么这个解法很妙？

• 降维优化：原本 O(N^4) 的状态被优化成 O(N^3)，因为 k 是 2N-1 级别的，而 i、j 都在 N 级别的范围内。
• 动态规划思维：这题很容易想成回溯（暴力搜索），但你会发现可行路径太多，根本跑不完。DP 让计算量可控，并且用 max 记录最优解。
• 障碍物处理：如果某个位置是 -1，直接跳过，不影响后续的状态转移。

如果你觉得这道题难，那你可以想象成：

• 你和老板去开会，老板选一个会议室，你选另一个，目标是尽可能多地收集客户的好评（樱桃）。当然，如果你们俩都选了同一个会议室，那就只算一次好评，毕竟“团队合作”嘛😂。
• 这题和现实很像：做技术的我们，总想“多摘点樱桃”（多写点代码、学点新东西），但现实往往给你丢几个障碍物 -1（如奇怪的需求、老板的突发奇想）。但只要规划好路径，少走弯路，就能摘到最多的果实！🍒🍒🍒