LeetCode 题解工作台
最多可收集的水果数目
有一个游戏，游戏由 n x n 个房间网格状排布组成。 给你一个大小为 n x n 的二维整数数组 fruits ，其中 fruits[i][j] 表示房间 (i, j) 中的水果数目。有三个小朋友 一开始 分别从角落房间 (0, 0) ， (0, n - 1) 和 (n - 1, 0) 出发。 C…
3
题型
6
代码语言
3
相关题
当前训练重点
困难 · 状态·转移·动态规划
答案摘要
根据题目描述，从 $(0, 0)$ 出发的小朋友要想在 $n - 1$ 步后到达 $(n - 1, n - 1)$，那么他只能走主对角线上的房间 $(i, i)$，即 $i = 0, 1, \ldots, n - 1$。而从 $(0, n - 1)$ 出发的小朋友只能走主对角线以上的房间，而从 $(n - 1, 0)$ 出发的小朋友只能走主对角线以下的房间。这意味着三个小朋友除了在 $(n - 1…
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 状态·转移·动态规划 题型思路
题目描述
有一个游戏，游戏由 n x n 个房间网格状排布组成。
给你一个大小为 n x n 的二维整数数组 fruits ，其中 fruits[i][j] 表示房间 (i, j) 中的水果数目。有三个小朋友 一开始 分别从角落房间 (0, 0) ，(0, n - 1) 和 (n - 1, 0) 出发。
每一位小朋友都会 恰好 移动 n - 1 次，并到达房间 (n - 1, n - 1) ：
- 从
(0, 0)出发的小朋友每次移动从房间(i, j)出发，可以到达(i + 1, j + 1)，(i + 1, j)和(i, j + 1)房间之一（如果存在）。 - 从
(0, n - 1)出发的小朋友每次移动从房间(i, j)出发，可以到达房间(i + 1, j - 1)，(i + 1, j)和(i + 1, j + 1)房间之一（如果存在）。 - 从
(n - 1, 0)出发的小朋友每次移动从房间(i, j)出发，可以到达房间(i - 1, j + 1)，(i, j + 1)和(i + 1, j + 1)房间之一（如果存在）。
当一个小朋友到达一个房间时，会把这个房间里所有的水果都收集起来。如果有两个或者更多小朋友进入同一个房间，只有一个小朋友能收集这个房间的水果。当小朋友离开一个房间时，这个房间里不会再有水果。
请你返回三个小朋友总共 最多 可以收集多少个水果。
示例 1：
输入：fruits = [[1,2,3,4],[5,6,8,7],[9,10,11,12],[13,14,15,16]]
输出：100
解释：
这个例子中：
- 第 1 个小朋友（绿色）的移动路径为
(0,0) -> (1,1) -> (2,2) -> (3, 3)。 - 第 2 个小朋友（红色）的移动路径为
(0,3) -> (1,2) -> (2,3) -> (3, 3)。 - 第 3 个小朋友（蓝色）的移动路径为
(3,0) -> (3,1) -> (3,2) -> (3, 3)。
他们总共能收集 1 + 6 + 11 + 16 + 4 + 8 + 12 + 13 + 14 + 15 = 100 个水果。
示例 2：
输入：fruits = [[1,1],[1,1]]
输出：4
解释：
这个例子中：
- 第 1 个小朋友移动路径为
(0,0) -> (1,1)。 - 第 2 个小朋友移动路径为
(0,1) -> (1,1)。 - 第 3 个小朋友移动路径为
(1,0) -> (1,1)。
他们总共能收集 1 + 1 + 1 + 1 = 4 个水果。
提示：
2 <= n == fruits.length == fruits[i].length <= 10000 <= fruits[i][j] <= 1000
解题思路
方法一：动态规划
根据题目描述，从 出发的小朋友要想在 步后到达 ，那么他只能走主对角线上的房间 ，即 。而从 出发的小朋友只能走主对角线以上的房间，而从 出发的小朋友只能走主对角线以下的房间。这意味着三个小朋友除了在 到达终点外，其他房间都不会有多个小朋友重复进入。
我们可以用动态规划的方式，计算从 和 出发的小朋友达到 时，能收集到的水果数。定义 表示小朋友到达 时能收集到的水果数。
对于从 出发的小朋友，状态转移方程为：
注意，只有当 时， 才是有效的。
对于从 出发的小朋友，状态转移方程为：
同样，只有当 时， 才是有效的。
最后，答案为 ，即主对角线上的水果数加上两个小朋友到达 和 时能收集到的水果数。
时间复杂度 ，空间复杂度 。其中 为房间的边长。
class Solution:
def maxCollectedFruits(self, fruits: List[List[int]]) -> int:
n = len(fruits)
f = [[-inf] * n for _ in range(n)]
f[0][n - 1] = fruits[0][n - 1]
for i in range(1, n):
for j in range(i + 1, n):
f[i][j] = max(f[i - 1][j], f[i - 1][j - 1]) + fruits[i][j]
if j + 1 < n:
f[i][j] = max(f[i][j], f[i - 1][j + 1] + fruits[i][j])
f[n - 1][0] = fruits[n - 1][0]
for j in range(1, n):
for i in range(j + 1, n):
f[i][j] = max(f[i][j - 1], f[i - 1][j - 1]) + fruits[i][j]
if i + 1 < n:
f[i][j] = max(f[i][j], f[i + 1][j - 1] + fruits[i][j])
return sum(fruits[i][i] for i in range(n)) + f[n - 2][n - 1] + f[n - 1][n - 2]
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | O(n^2) |
| 空间 | O(n) |
面试官常问的追问
外企场景- question_mark
Look for candidates who can efficiently handle state transitions and understand the dynamic programming pattern.
- question_mark
Candidates should focus on optimizing space complexity while managing the three-child scenario in the grid.
- question_mark
Pay attention to how candidates explain the state representation and the grid traversal approach.
常见陷阱
外企场景- error
Candidates may overlook the optimization of state transitions and end up with a less efficient solution.
- error
A common mistake is not managing the three children's movement separately, leading to incorrect fruit calculations.
- error
Some may attempt a brute force solution that leads to time or space complexity issues, especially with larger grids.
进阶变体
外企场景- arrow_right_alt
Reduce the number of children or increase the grid size to test the scalability of the solution.
- arrow_right_alt
Introduce obstacles or empty rooms to modify the grid and test the adaptability of the algorithm.
- arrow_right_alt
Allow the children to make fewer moves and explore how the solution changes with limited movement options.