Problem

There is a game dungeon comprised of n x n rooms arranged in a grid.

You are given a 2D array fruits of size n x n, where fruits[i][j] represents the number of fruits in the room (i, j). Three children will play in the game dungeon, with initial positions at the corner rooms (0, 0), (0, n - 1), and (n - 1, 0).

The children will make exactly n - 1 moves according to the following rules to reach the room (n - 1, n - 1):

  • The child starting from (0, 0) must move from their current room (i, j) to one of the rooms (i + 1, j + 1), (i + 1, j), and (i, j + 1) if the target room exists.
  • The child starting from (0, n - 1) must move from their current room (i, j) to one of the rooms (i + 1, j - 1), (i + 1, j), and (i + 1, j + 1) if the target room exists.
  • The child starting from (n - 1, 0) must move from their current room (i, j) to one of the rooms (i - 1, j + 1), (i, j + 1), and (i + 1, j + 1) if the target room exists.

When a child enters a room, they will collect all the fruits there. If two or more children enter the same room, only one child will collect the fruits, and the room will be emptied after they leave.

Return the maximum number of fruits the children can collect from the dungeon.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


Input: fruits = [[1,2,3,4],[5,6,8,7],[9,10,11,12],[13,14,15,16]]

Output: 100

Explanation:

![](https://assets.leetcode.com/uploads/2024/10/15/example_1.gif)

In this example:

  * The 1st child (green) moves on the path `(0,0) -> (1,1) -> (2,2) -> (3, 3)`.
  * The 2nd child (red) moves on the path `(0,3) -> (1,2) -> (2,3) -> (3, 3)`.
  * The 3rd child (blue) moves on the path `(3,0) -> (3,1) -> (3,2) -> (3, 3)`.

In total they collect `1 + 6 + 11 + 16 + 4 + 8 + 12 + 13 + 14 + 15 = 100`
fruits.

Example 2

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


Input: fruits = [[1,1],[1,1]]

Output: 4

Explanation:

In this example:

  * The 1st child moves on the path `(0,0) -> (1,1)`.
  * The 2nd child moves on the path `(0,1) -> (1,1)`.
  * The 3rd child moves on the path `(1,0) -> (1,1)`.

In total they collect `1 + 1 + 1 + 1 = 4` fruits.

Constraints

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

Solution

Method 1 – 3D Dynamic Programming (State Compression)

Intuition

Each child starts from a different corner and must reach the bottom-right corner in exactly n-1 moves, collecting fruits along the way. Since children can overlap, we need to avoid double-counting fruits. We can use dynamic programming to track the maximum fruits collected for each possible position of the three children at each step.

Approach

  1. Let dp[i][j][k] be the maximum fruits collected when:
    • Child 1 is at (i, j)
    • Child 2 is at (i, n-1-(j-i))
    • Child 3 is at (n-1-(j-i), j)
    • All have taken the same number of steps (i+j)
  2. For each move, try all possible next moves for each child, and update the DP accordingly, making sure not to double-count fruits if two or more children land on the same cell.
  3. The answer is the maximum value at the destination cell after n-1 moves.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
public:
    int maximumFruits(vector<vector<int>>& fruits) {
        int n = fruits.size();
        vector<vector<vector<int>>> dp(n, vector<vector<int>>(n, vector<int>(n, -1)));
        dp[0][0][0] = fruits[0][0] + fruits[0][n-1] + fruits[n-1][0];
        for(int step=1;step<n;++step) {
            vector<vector<vector<int>>> ndp(n, vector<vector<int>>(n, vector<int>(n, -1)));
            for(int i=0;i<n;++i) for(int j=0;j<n;++j) for(int k=0;k<n;++k) if(dp[i][j][k]>=0) {
                for(int di:{0,1}) for(int dj:{0,1}) for(int dk:{0,1}) {
                    int ni=i+di, nj=j+dj, nk=k+dk;
                    if(ni<n && nj<n && nk<n) {
                        set<pair<int,int>> pos = {{ni,ni},{nj,n-1-(nj-ni)},{n-1-(nk-nj),nk}};
                        int add=0;
                        for(auto [x,y]:pos) add+=fruits[x][y];
                        ndp[ni][nj][nk]=max(ndp[ni][nj][nk],dp[i][j][k]+add);
                    }
                }
            }
            dp=ndp;
        }
        return dp[n-1][n-1][n-1];
    }
};
1

// Omitted for brevity due to high complexity and memory usage
1

// Omitted for brevity due to high complexity and memory usage
1

// Omitted for brevity due to high complexity and memory usage
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution:
    def maximumFruits(self, fruits: list[list[int]]) -> int:
        n = len(fruits)
        from collections import defaultdict
        dp = defaultdict(lambda: -1)
        dp[(0,0,0)] = fruits[0][0] + fruits[0][n-1] + fruits[n-1][0]
        for step in range(1, n):
            ndp = defaultdict(lambda: -1)
            for i,j,k in dp:
                for di in (0,1):
                    ni = i+di
                    if ni>=n: continue
                    for dj in (0,1):
                        nj = j+dj
                        if nj>=n: continue
                        for dk in (0,1):
                            nk = k+dk
                            if nk>=n: continue
                            pos = {(ni,ni),(nj,n-1-(nj-ni)),(n-1-(nk-nj),nk)}
                            add = sum(fruits[x][y] for x,y in pos)
                            ndp[(ni,nj,nk)] = max(ndp[(ni,nj,nk)], dp[(i,j,k)]+add)
            dp = ndp
        return dp[(n-1,n-1,n-1)]
1

// Omitted for brevity due to high complexity and memory usage

1

// Omitted for brevity due to high complexity and memory usage

Complexity

  • ⏰ Time complexity: O(n^4), as we track all possible positions for three children at each step.
  • 🧺 Space complexity: O(n^3), for the DP table.