741. 摘樱桃

题目描述

输入 n x n 网格 grid。1 表示格子里有一颗樱桃，0 表示空地，-1 表示荆棘，荆棘格不能进入。

先从左上角 (0, 0) 出发，每步只能向右或向下，走到右下角 (n - 1, n - 1)；再从右下角出发，每步只能向左或向上，走回 (0, 0)。途中只能经过值为 0 或 1 的格子。

经过有樱桃的格子就摘下它，之后该格变为空地，所以同一颗樱桃只算一次。

返回往返一趟最多能摘到的樱桃数。如果左上角和右下角之间不存在可走的路径，返回 0。

示例 1

输入：grid = [[0,1,-1],[1,0,-1],[1,1,1]]
输出：5

解释：去程向下、向下、向右、向右摘到 4 颗，回程经过 (0,1) 再摘 1 颗，共 5 颗。

示例 2

输入：grid = [[1,1,-1],[1,-1,1],[-1,1,1]]
输出：0

解释：荆棘挡住了所有通往右下角的路线，只能返回 0。

数据范围

n == grid.length
n == grid[i].length
1 <= n <= 50
grid[i][j] 只取 -1、0、1。
grid[0][0] != -1
grid[n - 1][n - 1] != -1

解题思路

回程反过来看也是一条从 (0,0) 向右/向下的路线，所以问题等价于两个人 A、B 同时从起点出发。两人都走了 k 步时一定在同一条反对角线 x+y=k 上，只要记录两人的行号 x1、x2 就能确定位置。dp[x1][x2] 表示走 k 步后两人在这两个位置时最多摘到的樱桃数，由上一步四种移动组合转移而来；两人站在同一格时樱桃只算一次。

为什么正确

处理第 k 层时，dp 中保存的是两人恰好走了 k-1 步时所有状态的最优值，-1 表示不可达；对称性让我们只需计算 x1 <= x2。

复杂度分析

时间 O(n^3)，空间 O(n^2)（按层滚动）。

易错点

先贪心走一条最多樱桃的路，再在剩下的格子里走第二条，不一定最优；必须让两条路线同时决策。另外两人站在同一格时樱桃只能算一次。

参考代码

Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。

class Solution:
    def cherryPickup(self, grid: List[List[int]]) -> int:
        n = len(grid)
        dp = [[-1] * n for _ in range(n)]
        dp[0][0] = grid[0][0]
        for k in range(1, 2 * n - 1):
            nd = [[-1] * n for _ in range(n)]
            for x1 in range(max(0, k - n + 1), min(k, n - 1) + 1):
                for x2 in range(x1, min(k, n - 1) + 1):
                    y1, y2 = k - x1, k - x2
                    if grid[x1][y1] == -1 or grid[x2][y2] == -1:
                        continue
                    best = max(dp[x1][x2], dp[x1][x2 - 1] if x2 else -1)
                    if x1:
                        best = max(best, dp[x1 - 1][x2], dp[x1 - 1][x2 - 1])
                    if best < 0:
                        continue
                    nd[x1][x2] = best + grid[x1][y1] + (grid[x2][y2] if x1 != x2 else 0)
            dp = nd
        return max(dp[n - 1][n - 1], 0)

class Solution {
    public int cherryPickup(int[][] grid) {
        int n = grid.length;
        int[][] dp = new int[n][n];
        for (int[] row : dp) Arrays.fill(row, -1);
        dp[0][0] = grid[0][0];
        for (int k = 1; k < 2 * n - 1; k++) {
            int[][] nd = new int[n][n];
            for (int[] row : nd) Arrays.fill(row, -1);
            for (int x1 = Math.max(0, k - n + 1); x1 <= Math.min(k, n - 1); x1++) {
                for (int x2 = x1; x2 <= Math.min(k, n - 1); x2++) {
                    int y1 = k - x1, y2 = k - x2;
                    if (grid[x1][y1] == -1 || grid[x2][y2] == -1) {
                        continue;
                    }
                    int best = Math.max(dp[x1][x2], x2 > 0 ? dp[x1][x2 - 1] : -1);
                    if (x1 > 0) {
                        best = Math.max(best, Math.max(dp[x1 - 1][x2], dp[x1 - 1][x2 - 1]));
                    }
                    if (best < 0) {
                        continue;
                    }
                    nd[x1][x2] = best + grid[x1][y1] + (x1 != x2 ? grid[x2][y2] : 0);
                }
            }
            dp = nd;
        }
        return Math.max(dp[n - 1][n - 1], 0);
    }
}

class Solution {
public:
    int cherryPickup(vector<vector<int>>& grid) {
        int n = grid.size();
        vector<vector<int>> dp(n, vector<int>(n, -1));
        dp[0][0] = grid[0][0];
        for (int k = 1; k < 2 * n - 1; k++) {
            vector<vector<int>> nd(n, vector<int>(n, -1));
            for (int x1 = max(0, k - n + 1); x1 <= min(k, n - 1); x1++) {
                for (int x2 = x1; x2 <= min(k, n - 1); x2++) {
                    int y1 = k - x1, y2 = k - x2;
                    if (grid[x1][y1] == -1 || grid[x2][y2] == -1) {
                        continue;
                    }
                    int best = max(dp[x1][x2], x2 ? dp[x1][x2 - 1] : -1);
                    if (x1) {
                        best = max({best, dp[x1 - 1][x2], dp[x1 - 1][x2 - 1]});
                    }
                    if (best < 0) {
                        continue;
                    }
                    nd[x1][x2] = best + grid[x1][y1] + (x1 != x2 ? grid[x2][y2] : 0);
                }
            }
            dp = nd;
        }
        return max(dp[n - 1][n - 1], 0);
    }
};

func cherryPickup(grid [][]int) int {
	n := len(grid)
	newTable := func() [][]int {
		t := make([][]int, n)
		for i := range t {
			t[i] = make([]int, n)
			for j := range t[i] {
				t[i][j] = -1
			}
		}
		return t
	}
	dp := newTable()
	dp[0][0] = grid[0][0]
	for k := 1; k < 2*n-1; k++ {
		nd := newTable()
		for x1 := max(0, k-n+1); x1 <= min(k, n-1); x1++ {
			for x2 := x1; x2 <= min(k, n-1); x2++ {
				y1, y2 := k-x1, k-x2
				if grid[x1][y1] == -1 || grid[x2][y2] == -1 {
					continue
				}
				best := dp[x1][x2]
				if x2 > 0 {
					best = max(best, dp[x1][x2-1])
				}
				if x1 > 0 {
					best = max(best, dp[x1-1][x2], dp[x1-1][x2-1])
				}
				if best < 0 {
					continue
				}
				gain := grid[x1][y1]
				if x1 != x2 {
					gain += grid[x2][y2]
				}
				nd[x1][x2] = best + gain
			}
		}
		dp = nd
	}
	return max(dp[n-1][n-1], 0)
}

var cherryPickup = function(grid) {
    const n = grid.length;
    let dp = Array.from({ length: n }, () => new Array(n).fill(-1));
    dp[0][0] = grid[0][0];
    for (let k = 1; k < 2 * n - 1; k++) {
        const nd = Array.from({ length: n }, () => new Array(n).fill(-1));
        for (let x1 = Math.max(0, k - n + 1); x1 <= Math.min(k, n - 1); x1++) {
            for (let x2 = x1; x2 <= Math.min(k, n - 1); x2++) {
                const y1 = k - x1, y2 = k - x2;
                if (grid[x1][y1] === -1 || grid[x2][y2] === -1) {
                    continue;
                }
                let best = Math.max(dp[x1][x2], x2 ? dp[x1][x2 - 1] : -1);
                if (x1) {
                    best = Math.max(best, dp[x1 - 1][x2], dp[x1 - 1][x2 - 1]);
                }
                if (best < 0) {
                    continue;
                }
                nd[x1][x2] = best + grid[x1][y1] + (x1 !== x2 ? grid[x2][y2] : 0);
            }
        }
        dp = nd;
    }
    return Math.max(dp[n - 1][n - 1], 0);
};

function cherryPickup(grid: number[][]): number {
    const n = grid.length;
    let dp: number[][] = Array.from({ length: n }, () => new Array(n).fill(-1));
    dp[0][0] = grid[0][0];
    for (let k = 1; k < 2 * n - 1; k++) {
        const nd = Array.from({ length: n }, () => new Array(n).fill(-1));
        for (let x1 = Math.max(0, k - n + 1); x1 <= Math.min(k, n - 1); x1++) {
            for (let x2 = x1; x2 <= Math.min(k, n - 1); x2++) {
                const y1 = k - x1, y2 = k - x2;
                if (grid[x1][y1] === -1 || grid[x2][y2] === -1) {
                    continue;
                }
                let best = Math.max(dp[x1][x2], x2 ? dp[x1][x2 - 1] : -1);
                if (x1) {
                    best = Math.max(best, dp[x1 - 1][x2], dp[x1 - 1][x2 - 1]);
                }
                if (best < 0) {
                    continue;
                }
                nd[x1][x2] = best + grid[x1][y1] + (x1 !== x2 ? grid[x2][y2] : 0);
            }
        }
        dp = nd;
    }
    return Math.max(dp[n - 1][n - 1], 0);
}

载入编辑器，自己跑一遍 →

动态规划专题的其他题目

查看动态规划全部题目 →