Sponsored
Sponsored
We will approach the problem using dynamic programming by maintaining a 3D DP table. The idea is to simulate two individuals traversing the grid simultaneously: one moving from (0,0) to (n-1,n-1) and the other returning from (n-1,n-1) back to (0,0). Both will walk through cells to collect cherries with the understanding that a cell’s cherry can be collected only once.
The DP table, dp[x1][y1][x2], represents the maximum cherries collected when person 1 is at (x1,y1) and person 2 is at (x2,y1+x1-x2) such that both paths have used same number of steps. Transitions are explored based on valid grid movements (right or down) and allowed combinations.
This method ensures we utilize optimal substructure and memoization to avoid computing the same state multiple times.
Time Complexity: O(n^3), due to iterating through each position combination for both players.
Space Complexity: O(n^3), the space needed to store results of all position combinations.
1def cherryPickup(grid):
2 n = len(grid)
3 dp = [[[float('-inf')] * n for _ in range(n)] for _ in range(n)]
4
5 def is_valid(x, y):
6 return 0 <= x < n and 0 <= y < n and grid[x][y] != -1
7
8 dp[0][0][0] = grid[0][0]
9
10 for x1 in range(n):
11 for y1 in range(n):
12 for x2 in range(n):
13 y2 = x1 + y1 - x2
14 if is_valid(x1, y1) and is_valid(x2, y2):
15 cherries = grid[x1][y1]
16 if x1 != x2:
17 cherries += grid[x2][y2]
18
19 if x1 > 0:
20 dp[x1][y1][x2] = max(dp[x1][y1][x2], dp[x1-1][y1][x2] + cherries)
21 if y1 > 0:
22 dp[x1][y1][x2] = max(dp[x1][y1][x2], dp[x1][y1-1][x2] + cherries)
23 if x2 > 0:
24 dp[x1][y1][x2] = max(dp[x1][y1][x2], dp[x1][y1][x2-1] + cherries)
25 if y2 > 0:
26 dp[x1][y1][x2] = max(dp[x1][y1][x2], dp[x1][y1][x2] + cherries)
27
28 return max(0, dp[-1][-1][-1])The implemented solution uses a 3D DP array where each state is represented by the positions of two players (x1, y1, x2) which directly determines (x2, y2) due to the step count equality of x1+y1 and x2+y2. Each entry fills based on maximum cherries collectable given their current step scenario, striving to improve from all possible move origins (right or down).
Given the constraints of the initial approach, further space optimization can be applied by minimizing the dimensions that are updated in the DP table at any given time. We'll reduce our 3D DP array into a 2D array considering only necessary state information, as they relate to specific grid traversals. This lowering of space dimensions capitalizes on the symmetrical nature of path reversals without sacrificing calculation correctness or granularity.
Time Complexity: O(n^3), iterating through elements optimized per journey line level.
Space Complexity: O(n^2), condensing memos to one comprehensive 2D table pairing.
1def cherryPickup(grid):
2 n = len(grid)
This solution keeps updating the 2D DP table along each step of a journey, maintaining only pertinent states per each t (sum of (x1 + y1)) layer. This slimmed-down model reduces memory burden significantly by recycling layers in place of ever-expanding a 3D matrix, aligning closely with each movement's iterative aspect.