2025-06-13:最多可收集的水果数目。用go语言,有一个由 n x n 格子组成的游戏地图,每个格子代表一个房间。给定一个
2025-06-13:最多可收集的水果数目。用go语言,有一个由 n x n 格子组成的游戏地图,每个格子代表一个房间。给定一个二维数组 fruits,fruits[i][j] 表示房间 (i, j) 中的水果数量。
游戏中有三个小朋友,分别从以下三个起点出发:
-
小朋友A:起点为左上角房间 (0, 0)
-
小朋友B:起点为右上角房间 (0, n-1)
-
小朋友C:起点为左下角房间 (n-1, 0)
每个小朋友需要恰好移动 n-1 步,最终都到达右下角房间 (n-1, n-1)。
移动规则如下:
-
小朋友A 从 (i, j) 出发,可移动到 (i+1, j), (i, j+1), 或 (i+1, j+1) 中的一个(如果存在)
-
小朋友B 从 (i, j) 出发,可移动到 (i+1, j), (i+1, j-1), 或 (i+1, j+1) 中的一个(如果存在)
-
小朋友C 从 (i, j) 出发,可移动到 (i, j+1), (i-1, j+1), 或 (i+1, j+1) 中的一个(如果存在)
当小朋友进入某个房间时,会将该房间内所有的水果拾取。若多个小朋友同时进入同一房间,水果只计算一次(且只有一个人能拿走)。离开后该房间的水果数量为零。
请计算三位小朋友经过这些步骤后,能收集到的水果总数的最大值。
2 <= n == fruits.length == fruits[i].length <= 1000。
0 <= fruits[i][j] <= 1000。
输入: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 个水果。
题目来自力扣3363。
解题思路
-
路径不重叠时的最大水果数:
- 如果三个小朋友的路径完全不重叠,那么总水果数就是三个小朋友各自路径上的水果数之和。
- 这是理想情况,但通常路径会有重叠。
-
路径重叠时的处理:
- 如果多个小朋友经过同一个格子,该格子的水果只计算一次。
- 因此,我们需要找到三条路径,使得所有被覆盖的格子的水果数之和最大。
-
动态规划(DP):
- 用动态规划来计算每个小朋友从起点到终点的路径上能收集的最大水果数。
- 由于三个小朋友的移动规则不同,需要分别计算他们的路径。
-
对称性优化:
- 观察到小朋友B和小朋友C的路径可以通过对称性简化计算(如代码中通过交换
fruits
的上三角和下三角数据复用DP函数)。
- 观察到小朋友B和小朋友C的路径可以通过对称性简化计算(如代码中通过交换
具体步骤
-
初始化:
- 计算小朋友A的路径:从
(0, 0)
出发,每次可以向右、向下或向右下移动。 - 计算小朋友B的路径:从
(0, n-1)
出发,每次可以向下、向左下或向右下移动。 - 计算小朋友C的路径:从
(n-1, 0)
出发,每次可以向右、向右上或向右下移动。
- 计算小朋友A的路径:从
-
动态规划计算:
- 对于小朋友A:
- 定义
dpA[i][j]
表示从(0, 0)
到(i, j)
能收集的最大水果数。 - 状态转移:
dpA[i][j] = max(dpA[i-1][j], dpA[i][j-1], dpA[i-1][j-1]) + fruits[i][j]
。
- 定义
- 对于小朋友B:
- 定义
dpB[i][j]
表示从(0, n-1)
到(i, j)
能收集的最大水果数。 - 状态转移:
dpB[i][j] = max(dpB[i-1][j], dpB[i-1][j+1], dpB[i-1][j-1]) + fruits[i][j]
。
- 定义
- 对于小朋友C:
- 定义
dpC[i][j]
表示从(n-1, 0)
到(i, j)
能收集的最大水果数。 - 状态转移:
dpC[i][j] = max(dpC[i][j-1], dpC[i+1][j-1], dpC[i-1][j-1]) + fruits[i][j]
。
- 定义
- 对于小朋友A:
-
合并结果:
- 遍历所有可能的路径组合,计算三条路径覆盖的格子的水果数之和(重叠格子只计算一次)。
- 取最大值作为答案。
-
对称性优化:
- 由于小朋友B和小朋友C的路径是对称的,可以通过交换
fruits
的上三角和下三角数据复用DP函数(如代码所示)。
- 由于小朋友B和小朋友C的路径是对称的,可以通过交换
时间复杂度和空间复杂度
-
时间复杂度:
- 动态规划填充
dp
表的时间为 ( O(n^2) )(每个格子计算一次)。 - 需要分别计算三个小朋友的路径,但由于对称性优化,实际计算两次(小朋友A和小朋友B,小朋友C通过对称性复用)。
- 合并结果时可能需要遍历所有格子,最坏情况下为 ( O(n^2) )。
- 总时间复杂度:( O(n^2) )。
- 动态规划填充
-
空间复杂度:
- 需要存储
dp
表,大小为 ( O(n^2) )。 - 由于对称性优化,可以复用部分空间。
- 总空间复杂度:( O(n^2) )。
- 需要存储
总结
- 通过动态规划分别计算三个小朋友的路径。
- 利用对称性优化减少计算量。
- 最终合并结果时注意去重。
- 时间复杂度和空间复杂度均为 ( O(n^2) )。
Go完整代码如下:
.
package main
import (
"fmt"
"math"
)
func maxCollectedFruits(fruits [][]int) (ans int) {
n := len(fruits)
f := make([][]int, n-1)
for i := range f {
f[i] = make([]int, n+1)
}
dp := func() int {
for i := range f {
for j := range f[i] {
f[i][j] = math.MinInt
}
}
f[0][n-1] = fruits[0][n-1]
for i := 1; i < n-1; i++ {
for j := max(n-1-i, i+1); j < n; j++ {
f[i][j] = max(f[i-1][j-1], f[i-1][j], f[i-1][j+1]) + fruits[i][j]
}
}
return f[n-2][n-1]
}
for i, row := range fruits {
ans += row[i]
}
ans += dp()
// 把下三角形中的数据填到上三角形中
for i := range fruits {
for j := range i {
fruits[j][i] = fruits[i][j]
}
}
return ans + dp()
}
func main() {
fruits := [][]int{{1,1},{1,1}}
fmt.Println(maxCollectedFruits(fruits))
}
Python完整代码如下:
.
# -*-coding:utf-8-*-
import math
def max_collected_fruits(fruits):
n = len(fruits)
# 初始化二维数组 f
f = [[-math.inf] * (n + 1) for _ in range(n - 1)]
def dp():
# 初始化f
for i in range(n - 1):
for j in range(n + 1):
f[i][j] = -math.inf
f[0][n - 1] = fruits[0][n - 1]
for i in range(1, n - 1):
for j in range(max(n - 1 - i, i + 1), n):
f[i][j] = max(f[i - 1][j - 1], f[i - 1][j], f[i - 1][j + 1]) + fruits[i][j]
return f[n - 2][n - 1]
ans = 0
for i in range(n):
ans += fruits[i][i]
ans += dp()
# 把下三角形的数据填到上三角形中
for i in range(n):
for j in range(i):
fruits[j][i] = fruits[i][j]
ans += dp()
return ans
if __name__ == "__main__":
fruits = [[1, 1], [1, 1]]
print(max_collected_fruits(fruits))
- 点赞
- 收藏
- 关注作者
评论(0)