LeetCode 741. 摘樱桃
题目描述
✅ 741. 摘樱桃
题意分析
在方阵中从左上角出发，只向右或向下走到右下角，再只向左或向上返回。
-1是不能经过的障碍，0是空格，1是只能采摘一次的樱桃。求往返合计最多能摘多少；没有完整可行路径时返回 0。
解法：同步双路径动态规划
核心思路
[!blue]
把回程反向看，它也是一条从左上到右下、只向右或向下的路径。因此问题等价于两个人从起点同步走到终点，最大化两条路径覆盖的樱桃总数，同一格只计算一次。两条路径允许重合，不能先单独选一条最优去程再固定它求回程。
走了
t步后，任何人的位置都满足row+col = t。固定步数时只需记录两人的行号r1、r2，列号由c1 = t-r1、c2 = t-r2得到。当前层的ndp[r1][r2]保存两人到达这两个位置的最大收益，dp则保存第t-1层，供当前层读取前驱。每个人只能从左侧或上方到达当前格，前一行号分别是
r或r-1，所以两人共有四种前驱组合。取其中可达状态的最大收益，再加当前格的樱桃：若r1 == r2，两人列号也相等，只加一格；否则加两格。位置越界或任意一人遇到障碍时，这个状态不可达。只在同一步检查重合就能完成整条路径的去重，因为同一个格子的行列和固定，两人若都经过它，一定在同一步到达。未来步数更大，也不可能再次经过已计入的格子，因此同一状态只保留最大历史收益，不需要记录此前摘过哪些樱桃。
初始两人同在起点，只有
dp[0][0] = grid[0][0]可达，其余位置设为负无穷；题目保证起点和终点不是障碍。每层重新建立全为负无穷的ndp，只从可达前驱转移，避免把不可达状态当作收益为 0 的路径。行号范围由0 <= r < n和0 <= t-r < n共同确定，即[max(0, t-n+1), min(n-1, t)]。两人走完
2*(n-1)步时都应位于终点，答案为dp[n-1][n-1]；它若仍不可达就返回 0。只有一个格子时无需转移，起点樱桃也只计一次。
解题步骤
- 初始化两人同在起点的状态。
- 按步数逐层创建不可达的新状态表。
- 枚举两人的合法行号，跳过障碍，并从四种前驱取得最大值。
- 增加本步新增樱桃数，结束后将无法到达终点的结果转换为零。
代码实现
class Solution {
public int cherryPickup(int[][] grid) {
int n = grid.length;
int negInf = Integer.MIN_VALUE / 4;
int[][] dp = new int[n][n];
for (int[] row : dp) {
Arrays.fill(row, negInf);
}
dp[0][0] = grid[0][0];
for (int t = 1; t <= 2 * (n - 1); t++) {
int[][] ndp = new int[n][n];
for (int[] row : ndp) {
Arrays.fill(row, negInf);
}
int rMin = Math.max(0, t - (n - 1));
int rMax = Math.min(n - 1, t);
for (int r1 = rMin; r1 <= rMax; r1++) {
for (int r2 = rMin; r2 <= rMax; r2++) {
// 同步步数等于行列下标之和，记录行号即可推出列号。
int c1 = t - r1;
int c2 = t - r2;
if (c1 < 0 || c1 >= n || c2 < 0 || c2 >= n) {
continue;
}
if (grid[r1][c1] == -1 || grid[r2][c2] == -1) {
continue;
}
int cherries = grid[r1][c1];
// 同一步行号相同就位于同一格，该格樱桃只计一次。
if (r1 != r2) {
cherries += grid[r2][c2];
}
// 两人各自来自上方或左方，共枚举四种前驱组合。
int best = negInf;
for (int dr1 = 0; dr1 <= 1; dr1++) {
for (int dr2 = 0; dr2 <= 1; dr2++) {
int pr1 = r1 - dr1;
int pr2 = r2 - dr2;
if (pr1 < 0 || pr2 < 0) {
continue;
}
best = Math.max(best, dp[pr1][pr2]);
}
}
if (best != negInf) {
ndp[r1][r2] = Math.max(ndp[r1][r2], best + cherries);
}
}
}
dp = ndp;
}
return Math.max(0, dp[n - 1][n - 1]);
}
}
func cherryPickup(grid [][]int) int {
n := len(grid)
const negInf = -1 << 60
dp := make([][]int, n)
for i := range dp {
dp[i] = make([]int, n)
for j := range dp[i] {
dp[i][j] = negInf
}
}
dp[0][0] = grid[0][0]
for t := 1; t <= 2*(n-1); t++ {
ndp := make([][]int, n)
for i := range ndp {
ndp[i] = make([]int, n)
for j := range ndp[i] {
ndp[i][j] = negInf
}
}
rMin := max741(0, t-(n-1))
rMax := min741(t, n-1)
for r1 := rMin; r1 <= rMax; r1++ {
for r2 := rMin; r2 <= rMax; r2++ {
// 同步步数等于行列下标之和，记录行号即可推出列号。
c1 := t - r1
c2 := t - r2
if c1 >= n || c2 >= n || grid[r1][c1] == -1 || grid[r2][c2] == -1 {
continue
}
cherries := grid[r1][c1]
// 同一步行号相同就位于同一格，该格樱桃只计一次。
if r1 != r2 {
cherries += grid[r2][c2]
}
// 两人各自来自上方或左方，共枚举四种前驱组合。
best := negInf
for _, dr1 := range []int{
0,
1,
} {
for _, dr2 := range []int{
0,
1,
} {
pr1, pr2 := r1-dr1, r2-dr2
if pr1 >= 0 && pr2 >= 0 && dp[pr1][pr2] != negInf {
if dp[pr1][pr2] > best {
best = dp[pr1][pr2]
}
}
}
}
if best != negInf && best+cherries > ndp[r1][r2] {
ndp[r1][r2] = best + cherries
}
}
}
dp = ndp
}
if dp[n-1][n-1] < 0 {
return 0
}
return dp[n-1][n-1]
}
func max741(a, b int) int {
if a > b {
return a
}
return b
}
func min741(a, b int) int {
if a < b {
return a
}
return b
}
复杂度分析
- 时间复杂度：$O(n^3)$，
n为方阵边长，步数为 $O(n)$，每层枚举 $O(n^2)$ 对位置并检查四个前驱。- 空间复杂度：$O(n^2)$，仅保留相邻两层状态。
关键点总结
[!green]
- 同步步数消去两个列坐标，将状态降到三维并滚动存储。
- 两条路径可以重合，限制只是同一樱桃不能重复计数。
- 不可达状态与合法的零收益状态需要区分。
易错点总结
[!yellow]
- 先贪心选去程，再求最佳回程：去程局部最优不保证两条路径并集最大。
- 同格仍把两人的樱桃都相加：重复计数。
- 原地更新本层状态：可能混入已经属于当前步数的结果。
- 把没有完整路径的负哨兵直接返回：题目要求此时返回零。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 1463. 摘樱桃 II | 困难 | 同样用两名同步移动者避免独立路径重复计分，原题每步向下一行，本题按相同总步数同步。 |
| 64. 最小路径和 | 中等 | 单条最优路径DP是基础，本题两条路径可能共享格子且只能计一次，不能独立求两次最优。 |