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] <= 1000This approach utilizes a three-dimensional dynamic programming array to store results. We consider a state dp[i][j][k] where:
Due to rule-specific movements and considering conflicts (i.e., only one child can collect the fruits from a room at a time), this DP array allows tracking of the optimal number of fruits collected in different scenarios, and eventually handles dimensional overlap by ensuring each cell sum is added only once when concurrent visits happen.
This Python solution defines a function maxFruitsDP which initializes a 3D DP array with all values set to -1 (indicating non-computed states). Starting from the initial state at (0,0,0) reflecting the starting positions of the children, the recursive state transition builds on previously computed maximum fruits, while managing overlaps through a set for unique fruit rooms.
JavaScript
Time Complexity: O(n^3) as each of the three indices i, j, and k can vary independently across n states.
Space Complexity: O(n^3) because the DP state uses a 3D array for storing intermediary results.
This method involves a depth-first recursive search of possible moves, leveraging memoization to store previously computed results for unique (i, j, k) states. It starts each child from their respective initial positions. It attempts all paths valid per child movement rules and combines reachable paths, while strategically caching results to prevent redundant computations.
Here, a recursive function dfs is defined that performs the depth-first search, exploring all valid transition states for the children concurrently, keeping track of fruits using memoization states in a 3D vector. The memo array is initially filled with -1 to represent unvisited states.
Java
Time Complexity: O(n^3) due to caching in memoization, preventing redundant traversals through previously solved states.
Space Complexity: O(n^3) for memoization storage, slightly alleviated by recursive stack space use.
| Approach | Complexity |
|---|---|
| Dynamic Programming with Three-dimensional DP Array | Time Complexity: O(n^3) as each of the three indices i, j, and k can vary independently across n states. Space Complexity: O(n^3) because the DP state uses a 3D array for storing intermediary results. |
| Recursive DFS with Memoization | Time Complexity: O(n^3) due to caching in memoization, preventing redundant traversals through previously solved states. Space Complexity: O(n^3) for memoization storage, slightly alleviated by recursive stack space use. |
Fruits into Basket - Leetcode 904 - Python • NeetCodeIO • 25,299 views views
Watch 9 more video solutions →Practice Find the Maximum Number of Fruits Collected with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor