沈阳公司网站建设全球网站流量查询
三个小朋友收集水果问题：最大水果收集路径
问题描述
有一个游戏，游戏由 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 + 1, j + 1)、(i + 1, j)或(i, j + 1)（如果存在）。 - 第二个小朋友 从
(0, n - 1)出发，每次可以选择移动到(i + 1, j - 1)、(i + 1, j)或(i + 1, j + 1)（如果存在）。 - 第三个小朋友 从
(n - 1, 0)出发，每次可以选择移动到(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 + 1 + 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 个水果。
思路分析
- 了解移动规则
第一个小朋友的路径是沿对角线移动的。因为每个格子只能被收集一次，第二个小朋友的最优路径应该是从(0, n-1)移动到(n-2, n-1)，并且不能越过主对角线。因此，最优解中第二个小朋友一定不会碰到主对角线。
需要特别处理如何从(n-2, n-1)出发，并且确保最终能精确到达(0, n-1)。每次规划路径时，我们需要确保每个小朋友的路径不会重叠，并且他们的水果收集路径最大化。 - 边界条件处理
对于第二个小朋友，最关键的是每次的 j 必须满足j >= n - 1 - i，确保路径不会越过对角线。
通过递归和记忆化搜索的方式，计算每个小朋友的最大水果收集数量。 - 动态规划实现
通过递归和记忆化搜索，我们可以解决这个问题。下面是实现代码：
class Solution {
public:int maxCollectedFruits(vector<vector<int>>& fruits) {int n = fruits.size(), res = 0;vector<vector<int>> memo(n, vector<int>(n, -1)); // 记忆化数组// 记忆化搜索函数function<int(int, int)> dfs = [&](int r, int c) -> int {if (r == 0) return fruits[r][c];if (memo[r][c] != -1) return memo[r][c]; // 如果已计算，直接返回for (int i = -1; i <= 1; i++) {int y = c + i;if (y >= n || y < n - 1 - (r - 1)) continue; // 确保列范围合法memo[r][c] = max(memo[r][c], dfs(r - 1, y) + fruits[r][c]);}return memo[r][c];};// 计算第一个小朋友的收集水果for (int i = 0; i < n; i++) {res += fruits[i][i];}res += dfs(n - 2, n - 1); // 从下往上走，第二个小朋友的收集路径// 将下三角形的数据填充到上三角for (int i = 0; i < n; i++) {for (int j = i; j < n; j++) {fruits[i][j] = fruits[j][i];}}// 重置memo数组并计算第三个小朋友的收集路径std::fill_n(memo.begin(), n, std::vector<int>(n, -1));res += dfs(n - 2, n - 1);return res;}
};
- 思路总结
记忆化搜索：通过递归的方式计算每个小朋友的最大水果收集数量，并利用记忆化缓存避免重复计算。
路径规划：根据每个小朋友的移动规则，避免路径重叠，并确保每个小朋友能够最大化收集水果。
矩阵转置：对于第二个小朋友和第三个小朋友，可以通过对矩阵进行转置操作，简化计算。