Hard

题目描述

有一个由 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

示例 2：

输入：fruits = [[1,1],[1,1]]
输出：4

约束：

  • 2 <= n == fruits.length == fruits[i].length <= 1000
  • 0 <= fruits[i][j] <= 1000

解题思路

这道题的关键观察是：从 (0,0) 开始的第一个孩子的路径是固定的，只能沿着对角线移动到 (n-1,n-1)。因此我们可以将问题分解为三个独立的子问题：

  1. 第一个孩子（从(0,0)开始）：只能沿对角线移动，路径唯一，直接累加对角线上的水果即可。

  2. 第二个孩子（从(0,n-1)开始）：需要到达 (n-1,n-1)，但要避开第一个孩子的路径。使用动态规划求解在有效区域内的最大收益路径。

  3. 第三个孩子（从(n-1,0)开始）：同样需要到达 (n-1,n-1)，避开前两个孩子的路径。

核心思路：

  • 第一个孩子的路径固定，收集对角线水果
  • 第二、三个孩子分别在各自的有效移动区域内使用动态规划
  • 第二个孩子的有效区域：上三角区域（不包括对角线）
  • 第三个孩子的有效区域：下三角区域（不包括对角线和第二个孩子可能经过的区域）

对于每个孩子，我们使用二维DP数组记录到达每个位置能收集的最大水果数，根据移动规则进行状态转移。

代码实现

class Solution {
public:
    int maxCollectedFruits(vector<vector<int>>& fruits) {
        int n = fruits.size();
        int result = 0;
        
        // Child 1: diagonal path (0,0) to (n-1,n-1)
        for (int i = 0; i < n; i++) {
            result += fruits[i][i];
        }
        
        // Child 2: from (0,n-1) to (n-1,n-1)
        vector<vector<int>> dp2(n, vector<int>(n, -1));
        dp2[0][n-1] = fruits[0][n-1];
        
        for (int i = 0; i < n-1; i++) {
            for (int j = 0; j < n; j++) {
                if (dp2[i][j] == -1) continue;
                // Three possible moves: (i+1,j-1), (i+1,j), (i+1,j+1)
                for (int dj = -1; dj <= 1; dj++) {
                    int ni = i + 1, nj = j + dj;
                    if (ni < n && nj >= 0 && nj < n && nj > ni) { // valid and in upper triangle
                        dp2[ni][nj] = max(dp2[ni][nj], dp2[i][j] + fruits[ni][nj]);
                    }
                }
            }
        }
        result += dp2[n-1][n-1];
        
        // Child 3: from (n-1,0) to (n-1,n-1)
        vector<vector<int>> dp3(n, vector<int>(n, -1));
        dp3[n-1][0] = fruits[n-1][0];
        
        for (int i = n-1; i >= 1; i--) {
            for (int j = 0; j < n; j++) {
                if (dp3[i][j] == -1) continue;
                // Three possible moves: (i-1,j+1), (i,j+1), (i+1,j+1)
                vector<pair<int,int>> moves = {{i-1,j+1}, {i,j+1}, {i+1,j+1}};
                for (auto [ni, nj] : moves) {
                    if (ni >= 0 && ni < n && nj >= 0 && nj < n && ni > nj) { // valid and in lower triangle
                        dp3[ni][nj] = max(dp3[ni][nj], dp3[i][j] + fruits[ni][nj]);
                    }
                }
            }
        }
        result += dp3[n-1][n-1];
        
        return result;
    }
};

class Solution:
    def maxCollectedFruits(self, fruits: List[List[int]]) -> int:
        n = len(fruits)
        result = 0
        
        # Child 1: diagonal path (0,0) to (n-1,n-1)
        for i in range(n):
            result += fruits[i][i]
        
        # Child 2: from (0,n-1) to (n-1,n-1)
        dp2 = [[-1] * n for _ in range(n)]
        dp2[0][n-1] = fruits[0][n-1]
        
        for i in range(n-1):
            for j in range(n):
                if dp2[i][j] == -1:
                    continue
                # Three possible moves: (i+1,j-1), (i+1,j), (i+1,j+1)
                for dj in [-1, 0, 1]:
                    ni, nj = i + 1, j + dj
                    if 0 <= ni < n and 0 <= nj < n and nj > ni:  # valid and in upper triangle
                        dp2[ni][nj] = max(dp2[ni][nj], dp2[i][j] + fruits[ni][nj])
        
        result += dp2[n-1][n-1]
        
        # Child 3: from (n-1,0) to (n-1,n-1)
        dp3 = [[-1] * n for _ in range(n)]
        dp3[n-1][0] = fruits[n-1][0]
        
        for i in range(n-1, 0, -1):
            for j in range(n):
                if dp3[i][j] == -1:
                    continue
                # Three possible moves: (i-1,j+1), (i,j+1), (i+1,j+1)
                moves = [(i-1, j+1), (i, j+1), (i+1, j+1)]
                for ni, nj in moves:
                    if 0 <= ni < n and 0 <= nj < n and ni > nj:  # valid and in lower triangle
                        dp3[ni][nj] = max(dp3[ni][nj], dp3[i][j] + fruits[ni][nj])
        
        result += dp3[n-1][n-1]
        
        return result

public class Solution {
    public int MaxCollectedFruits(int[][] fruits) {
        int n = fruits.Length;
        int result = 0;
        
        // Child 1: diagonal path (0,0) to (n-1,n-1)
        for (int i = 0; i < n; i++) {
            result += fruits[i][i];
        }
        
        // Child 2: from (0,n-1) to (n-1,n-1)
        int[,] dp2 = new int[n, n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                dp2[i, j] = -1;
            }
        }
        dp2[0, n-1] = fruits[0][n-1];
        
        for (int i = 0; i < n-1; i++) {
            for (int j = 0; j < n; j++) {
                if (dp2[i, j] == -1) continue;
                // Three possible moves: (i+1,j-1), (i+1,j), (i+1,j+1)
                for (int dj = -1; dj <= 1; dj++) {
                    int ni = i + 1, nj = j + dj;
                    if (ni < n && nj >= 0 && nj < n && nj > ni) { // valid and in upper triangle
                        dp2[ni, nj] = Math.Max(dp2[ni, nj], dp2[i, j] + fruits[ni][nj]);
                    }
                }
            }
        }
        result += dp2[n-1, n-1];
        
        // Child 3: from (n-1,0) to (n-1,n-1)
        int[,] dp3 = new int[n, n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                dp3[i, j] = -1;
            }
        }
        dp3[n-1, 0] = fruits[n-1][0];
        
        for (int i = n-1; i >= 1; i--) {
            for (int j = 0; j < n; j++) {
                if (dp3[i, j] == -1) continue;
                // Three possible moves: (i-1,j+1), (i,j+1), (i+1,j+1)
                int[,] moves = {{i-1, j+1}, {i, j+1}, {i+1, j+1}};
                for (int k = 0; k < 3; k++) {
                    int ni = moves[k, 0], nj = moves[k, 1];
                    if (ni >= 0 && ni < n && nj >= 0 && nj < n && ni > nj) { // valid and in lower triangle
                        dp3[ni, nj] = Math.Max(dp3[ni, nj], dp3[i, j] + fruits[ni][nj]);
                    }
                }
            }
        }
        result += dp3[n-1, n-1];
        
        return result;
    }
}

var maxCollectedFruits = function(fruits) {
    const n = fruits.length;
    
    // Child 1: (0,0) to (n-1,n-1) - diagonal path
    let child1Total = 0;
    for (let i = 0; i < n; i++) {
        child1Total += fruits[i][i];
    }
    
    // Child 2: (0,n-1) to (n-1,n-1) - DP for upper triangle
    let dp2 = Array(n).fill().map(() => Array(n).fill(-Infinity));
    dp2[0][n-1] = fruits[0][n-1];
    
    for (let i = 1; i < n; i++) {
        for (let j = 0; j < n; j++) {
            if (dp2[i-1][j] !== -Infinity) {
                // Move to (i, j-1), (i, j), (i, j+1)
                for (let dj = -1; dj <= 1; dj++) {
                    let nj = j + dj;
                    if (nj >= 0 && nj < n && !(i === nj)) { // avoid diagonal
                        dp2[i][nj] = Math.max(dp2[i][nj], dp2[i-1][j] + fruits[i][nj]);
                    }
                }
            }
        }
    }
    
    // Child 3: (n-1,0) to (n-1,n-1) - DP for lower triangle
    let dp3 = Array(n).fill().map(() => Array(n).fill(-Infinity));
    dp3[n-1][0] = fruits[n-1][0];
    
    for (let j = 1; j < n; j++) {
        for (let i = 0; i < n; i++) {
            if (dp3[i][j-1] !== -Infinity) {
                // Move to (i-1, j), (i, j), (i+1, j)
                for (let di = -1; di <= 1; di++) {
                    let ni = i + di;
                    if (ni >= 0 && ni < n && !(ni === j)) { // avoid diagonal
                        dp3[ni][j] = Math.max(dp3[ni][j], dp3[i][j-1] + fruits[ni][j]);
                    }
                }
            }
        }
    }
    
    return child1Total + dp2[n-1][n-1] + dp3[n-1][n-1];
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

指标复杂度
时间-
空间-