解决方案动态规划思路和算法由于从 ( N−1 , N−1 )返回 (0 , 0)的这条路径可以等价地看成从 (0 , 0)到 (N−1 , N−1) 的路径因此问题可以等价转换成有两个人从0 , 0) 出发向下或向右走到 (N−1 , N−1) 时摘到的樱桃个数之和的最大值。由于题目限制同一个格子只能摘取一次我们需要找到一种方案来判断两人是否到达了同一个格子。不妨假设两人同时出发且速度相同。无论这两人怎么走在时间相同的情况下他们向右走的步数加上向下走的步数之和是一个定值设为 k 。设两人的坐标为 (x1 , y1)和x2 y2则 x1 y1 x2 y2 k ,那么当 x1 x2 时必然有 y1 y2 ,即两个人到达了同一个格子。定义 f[k][x1][x2] 表示两个人设为A 和 B分别从(x1 , k−x1)和 (x2 , k−x2) 同时出发到达 (N−1 , N−1) 摘到的樱桃个数之和的最大值。如果 (x1 , k−x1) 或 (x2 , k−x2)是荆棘则 f[k][x1][x2] −∞f 表示不合法的情况。枚举 A 和 B 上一步的走法来计算 f[k][x1][x2] 有四种情况都往右从 f[k−1][x1][x2]转移过来A 往下B 往右从 f[k−1][x1−1][x2] 转移过来A 往右B 往下从 f[k−1][x1][x2−1]f 转移过来都往下从 f[k−1][x1−1][x2−1] 转移过来取这四种情况的最大值加上 grid[x1][k−x1] 和 grid[x2][k−x2] 的值就得到了 f[k][x1][x2] 如果 x1 x2 则只需加上 grid[x1][k−x1] 最后答案为 max⁡(f[2n−2][n−1][n−1] , 0)取 max⁡ 是因为路径可能被荆棘挡住无法从 (0 , 0) 到达 (N−1 , N−1)。代码实现时我们可以将 A 和 B 走出的路径的上轮廓看成是 A 走出的路径下轮廓看成是 B 走出的路径即视作 A 始终不会走到 B 的下方则有 x1 ≤ x2 在代码实现时保证这一点可以减少循环次数。代码Python3class Solution: def cherryPickup(self, grid: List[List[int]]) - int: n len(grid) f [[[-inf] * n for _ in range(n)] for _ in range(n * 2 - 1)] f[0][0][0] grid[0][0] for k in range(1, n * 2 - 1): for x1 in range(max(k - n 1, 0), min(k 1, n)): y1 k - x1 if grid[x1][y1] -1: continue for x2 in range(x1, min(k 1, n)): y2 k - x2 if grid[x2][y2] -1: continue res f[k - 1][x1][x2] # 都往右 if x1: res max(res, f[k - 1][x1 - 1][x2]) # 往下往右 if x2: res max(res, f[k - 1][x1][x2 - 1]) # 往右往下 if x1 and x2: res max(res, f[k - 1][x1 - 1][x2 - 1]) # 都往下 res grid[x1][y1] if x2 ! x1: # 避免重复摘同一个樱桃 res grid[x2][y2] f[k][x1][x2] res return max(f[-1][-1][-1], 0)C#public class Solution { public int CherryPickup(int[][] grid) { int n grid.Length; int[,,] f new int[n * 2 - 1, n, n]; for (int i 0; i n * 2 - 1; i) { for (int j 0; j n; j) { for (int k 0; k n; k) { f[i, j, k] int.MinValue; } } } f[0, 0, 0] grid[0][0]; for (int k 1; k n * 2 - 1; k) { for (int x1 Math.Max(k - n 1, 0); x1 Math.Min(k, n - 1); x1) { int y1 k - x1; if (grid[x1][y1] -1) { continue; } for (int x2 x1; x2 Math.Min(k, n - 1); x2) { int y2 k - x2; if (grid[x2][y2] -1) { continue; } int res f[k - 1, x1, x2]; // 都往右 if (x1 0) { res Math.Max(res, f[k - 1, x1 - 1, x2]); // 往下往右 } if (x2 0) { res Math.Max(res, f[k - 1, x1, x2 - 1]); // 往右往下 } if (x1 0 x2 0) { res Math.Max(res, f[k - 1, x1 - 1, x2 - 1]); // 都往下 } res grid[x1][y1]; if (x2 ! x1) { // 避免重复摘同一个樱桃 res grid[x2][y2]; } f[k, x1, x2] res; } } } return Math.Max(f[n * 2 - 2, n - 1, n - 1], 0); } }