DeepSeek LeetCode 741.摘樱桃 public int cherryPickup(int[][] grid)

LeetCode 741 题「摘樱桃」是一个经典的动态规划问题，要求从左上角 (0,0) 出发，走到右下角 (N-1,N-1)，再返回左上角，沿途摘樱桃（每个格子最多摘一次），求最多能摘到的樱桃数量。网格中 1 表示樱桃，0 表示空地，-1 表示荆棘（不可走）。问题分析直接模拟往返两次会互相影响，因为第一次摘过的樱桃第二次就不能再摘了。一个巧妙的转换是：等价于两个人同时从 (0,0) 出发，都走到 (N-1,N-1)，两人同时移动，摘到的樱桃总数即为所求（因为来回路径的总和可以看作两条去程路径的和，且每个格子只能被计算一次）。这样我们只需要考虑两条路径在每一步的位置。动态规划思路设网格大小为 N，两人同时走，每人都走 K 步到达终点，K = N-1（因为从 (0,0) 到 (N-1,N-1) 需要向下和向右共 2*(N-1) 步？注意：步数的定义要小心。通常我们使用“走了多少步”来表示，但从 (0,0) 到 (N-1,N-1) 需要向下 N-1 次，向右 N-1 次，总共 2*(N-1) 步。如果两人同时出发，每人都走相同的步数 t，那么他们所在的位置 (x1, y1) 和 (x2, y2) 满足 x1 + y1 = t，x2 + y2 = t（因为每步只能向下或向右）。所以我们用 t 表示当前走过的步数，取值范围从 0 到 2*(N-1)。定义状态 dp[t][i1][i2] 表示两人都走了 t 步后，第一个人在 (i1, t-i1)，第二个人在 (i2, t-i2) 时，两人已经摘到的樱桃总数（每个格子只计一次）。注意要保证坐标合法且在网格内。状态转移第 t 步的状态可以由第 t-1 步的四种可能移动组合转移而来：· 第一个人从 (i1-1, t-1-i1+1?) 更准确地说：第 t-1 步时，第一个人的位置可能是 (i1-1, t-1-(i1-1))（即上一步向下）或 (i1, t-1-i1)（上一步向右），第二人类似。所以共有四种组合：都向下：dp[t-1][i1-1][i2-1]一向下、二向右：dp[t-1][i1-1][i2]一向右、二向下：dp[t-1][i1][i2-1]都向右：dp[t-1][i1][i2]取这些状态的最大值，然后加上当前位置的樱桃数。如果两人在同一格子 (i1 == i2)，则只加一次樱桃数（因为格子只能摘一次）；否则分别加各自格子的樱桃数。边界与合法性· 起点：t=0 时，两人都在 (0,0)，dp[0][0][0] = grid[0][0]（如果起点有樱桃）。· 必须确保每个位置不是荆棘（grid[i][j] != -1），否则该状态不可达，设为负无穷。· 最终答案是 max(0, dp[2*(N-1)][N-1][N-1])，因为两人最后都到达终点。但注意如果无法到达，返回 0。空间优化由于 t 只依赖于 t-1，可以使用滚动数组压缩一维，只保留 dp[i1][i2] 并迭代更新。但要注意更新顺序，避免覆盖。代码实现以下是完整的 Java 解法：classSolution{publicintcherryPickup(int[][]grid){intN=grid.length;intK=2*N-1;// 总步数（从0开始计数，t从0到2N-2）int[][][]dp=newint[K][N][N];// 初始化 dp 为最小值，表示不可达for(intt=0;tK;t++){for(inti=0;iN;i++){for(intj=0;jN;j++){dp[t][i][j]=Integer.MIN_VALUE;}}}dp[0][0][0]=grid[0][0];// 起点for(intt=1;tK;t++){for(inti1=0;i1N;i1++){for(inti2=0;i2