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):
(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.(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.(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.
Example 1:
Input: fruits = [[1,2,3,4],[5,6,8,7],[9,10,11,12],[13,14,15,16]]
Output: 100
Explanation:
In this example:
(0,0) -> (1,1) -> (2,2) -> (3, 3).(0,3) -> (1,2) -> (2,3) -> (3, 3).(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:
Input: fruits = [[1,1],[1,1]]
Output: 4
Explanation:
In this example:
(0,0) -> (1,1).(0,1) -> (1,1).(1,0) -> (1,1).In total they collect 1 + 1 + 1 + 1 = 4 fruits.
Constraints:
2 <= n == fruits.length == fruits[i].length <= 10000 <= fruits[i][j] <= 1000To solve #3363 Find the Maximum Number of Fruits Collected, the key idea is to model the problem as an optimization task where we explore possible states and maximize the fruits gathered under given constraints. A common strategy is to use dynamic programming to track the best result achievable for each valid state.
The DP state typically represents the current position or configuration and the number of fruits collected so far. At each step, transitions are evaluated based on allowed moves or choices, updating the maximum achievable value. Using memoization or a bottom-up DP table avoids recomputation and significantly improves performance. In many implementations, careful pruning of invalid states and efficient iteration over transitions are critical for passing large inputs.
The overall solution generally runs in polynomial time, depending on the number of states explored, while additional memory is used to store DP values. Thoughtful state design and transition optimization are essential for keeping the solution efficient.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Dynamic Programming with Memoization | O(n^3) | O(n^2) |
NeetCodeIO
Use these hints if you're stuck. Try solving on your own first.
The child at <code>(0, 0)</code> has only one possible path.
The other two children won’t intersect its path.
Use Dynamic Programming.
Watch expert explanations and walkthroughs
Jot down your thoughts, approach, and key learnings
Problems similar to Find the Maximum Number of Fruits Collected often appear in coding interviews because they test dynamic programming, state transitions, and optimization skills. Variations of such problems are frequently discussed in advanced interview preparation.
Dynamic programming tables or memoization maps are commonly used to store intermediate results. Depending on the implementation, arrays, hash maps, or matrices can represent the state space efficiently.
The optimal approach typically uses dynamic programming to track the maximum fruits that can be collected for each valid state or position. By caching intermediate results, the algorithm avoids recomputation and efficiently explores all feasible transitions.
The problem is considered hard because it involves designing an efficient state representation and exploring multiple transitions while maximizing a value. Handling constraints and optimizing the DP solution without excessive computation makes it challenging.