LeetCode 题解工作台
摘樱桃
给你一个 n x n 的网格 grid ，代表一块樱桃地，每个格子由以下三种数字的一种来表示： 0 表示这个格子是空的，所以你可以穿过它。 1 表示这个格子里装着一个樱桃，你可以摘到樱桃然后穿过它。 -1 表示这个格子里有荆棘，挡着你的路。 请你统计并返回：在遵守下列规则的情况下，能摘到的最多樱桃数…
3
题型
6
代码语言
3
相关题
当前训练重点
困难 · 状态·转移·动态规划
答案摘要
根据题目描述，玩家从 $(0, 0)$ 出发，到达 $(n-1, n-1)$ 后，又重新返回到起始点 $(0, 0)$，我们可以视为玩家两次从 $(0, 0)$ 出发，到达 $(n-1, n-1)$。 因此，我们定义 表示两次都走了 步，分别到达 $(i_1, k-i_1)$ 和 $(i_2, k-i_2)$ 时，能够摘到的最多樱桃数。初始时 $f[0][0][0] = grid[0][0]$…
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 状态·转移·动态规划 题型思路
题目描述
给你一个 n x n 的网格 grid ，代表一块樱桃地，每个格子由以下三种数字的一种来表示：
0表示这个格子是空的，所以你可以穿过它。1表示这个格子里装着一个樱桃，你可以摘到樱桃然后穿过它。-1表示这个格子里有荆棘，挡着你的路。
请你统计并返回：在遵守下列规则的情况下，能摘到的最多樱桃数：
- 从位置
(0, 0)出发，最后到达(n - 1, n - 1)，只能向下或向右走，并且只能穿越有效的格子（即只可以穿过值为0或者1的格子）； - 当到达
(n - 1, n - 1)后，你要继续走，直到返回到(0, 0)，只能向上或向左走，并且只能穿越有效的格子； - 当你经过一个格子且这个格子包含一个樱桃时，你将摘到樱桃并且这个格子会变成空的（值变为
0）； - 如果在
(0, 0)和(n - 1, n - 1)之间不存在一条可经过的路径，则无法摘到任何一个樱桃。
示例 1：
输入：grid = [[0,1,-1],[1,0,-1],[1,1,1]] 输出：5 解释：玩家从 (0, 0) 出发：向下、向下、向右、向右移动至 (2, 2) 。 在这一次行程中捡到 4 个樱桃，矩阵变成 [[0,1,-1],[0,0,-1],[0,0,0]] 。 然后，玩家向左、向上、向上、向左返回起点，再捡到 1 个樱桃。 总共捡到 5 个樱桃，这是最大可能值。
示例 2：
输入：grid = [[1,1,-1],[1,-1,1],[-1,1,1]] 输出：0
提示：
n == grid.lengthn == grid[i].length1 <= n <= 50grid[i][j]为-1、0或1grid[0][0] != -1grid[n - 1][n - 1] != -1
解题思路
方法一：动态规划
根据题目描述，玩家从 出发，到达 后，又重新返回到起始点 ，我们可以视为玩家两次从 出发，到达 。
因此，我们定义 表示两次都走了 步，分别到达 和 时，能够摘到的最多樱桃数。初始时 。其余 的初始值为负无穷。答案为 。
我们可以根据题目描述，得到状态转移方程：
其中 表示 和 位置上的樱桃数，而 分别表示 和 的前一步位置。
时间复杂度 ，空间复杂度 。其中 表示网格的边长。
class Solution:
def cherryPickup(self, grid: List[List[int]]) -> int:
n = len(grid)
f = [[[-inf] * n for _ in range(n)] for _ in range((n << 1) - 1)]
f[0][0][0] = grid[0][0]
for k in range(1, (n << 1) - 1):
for i1 in range(n):
for i2 in range(n):
j1, j2 = k - i1, k - i2
if (
not 0 <= j1 < n
or not 0 <= j2 < n
or grid[i1][j1] == -1
or grid[i2][j2] == -1
):
continue
t = grid[i1][j1]
if i1 != i2:
t += grid[i2][j2]
for x1 in range(i1 - 1, i1 + 1):
for x2 in range(i2 - 1, i2 + 1):
if x1 >= 0 and x2 >= 0:
f[k][i1][i2] = max(f[k][i1][i2], f[k - 1][x1][x2] + t)
return max(0, f[-1][-1][-1])
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | O(N^3) |
| 空间 | O(N^2) |
面试官常问的追问
外企场景- question_mark
Does the candidate clearly explain how dynamic programming is applied to track the states of both players and their transitions?
- question_mark
Can the candidate handle the constraints effectively, especially managing obstacles in the grid?
- question_mark
Is the candidate able to explain how they would optimize for both time and space complexity in this problem?
常见陷阱
外企场景- error
Failing to handle edge cases, such as when obstacles block all possible paths, leading to incorrect results.
- error
Incorrectly implementing the state transition logic, which could result in suboptimal paths or missing valid paths.
- error
Neglecting to properly update the DP table, which may cause inefficient state transitions and affect the maximum cherry count.
进阶变体
外企场景- arrow_right_alt
What if the grid has more than two players? Can the problem be generalized for multiple agents collecting cherries?
- arrow_right_alt
How would you adjust the solution for non-square grids or grids of varying dimensions?
- arrow_right_alt
What would happen if the player could only move in one direction at a time, or if diagonal movement was allowed?