This approach involves using a dynamic programming table to store intermediate results. The state dp[r][c1][c2] represents the maximum cherries we can collect when robot 1 is at position (r, c1) and robot 2 is at (r, c2). The transition involves moving both robots to the next row and trying all possible column moves for each robot.
Time Complexity: O(rows * cols^2)
Space Complexity: O(rows * cols^2)
1def cherryPickup(grid):
2 rows, cols = len(grid), len(grid[0])
3 dp = [[[0] * cols for _ in range(cols)] for _ in range(rows)]
4
5 for r in range(rows - 1, -1, -1):
6 for c1 in range(cols):
7 for c2 in range(cols):
8 for newC1 in [c1, c1 + 1, c1 - 1]:
9 for newC2 in [c2, c2 + 1, c2 - 1]:
10 if 0 <= newC1 < cols and 0 <= newC2 < cols:
11 prev = (dp[r + 1][newC1][newC2] if r + 1 < rows else 0)
12 dp[r][c1][c2] = max(dp[r][c1][c2], prev + grid[r][c1] + (grid[r][c2] if c1 != c2 else 0))
13 return dp[0][0][cols - 1]This function implements a dynamic programming solution. We use a 3D table dp where dp[r][c1][c2] represents the maximum cherries obtainable starting from row r with robot 1 at column c1 and robot 2 at column c2. We transition backwards from the last row to the first row, checking all possible moves for the robots.
This approach uses a recursive function with memoization to calculate the maximum cherries possible. The function recursively tries all valid ways the robots can move to the next row from their current columns, caching results to prevent redundant calculations.
Time Complexity: O(rows * cols^2)
Space Complexity: O(rows * cols^2) for memoization
1var cherryPickup = function(grid) {
2 const rows = grid.length, cols = grid[0].length;
3 const memo = Array.from({ length: rows }, () =>
4 Array.from({ length: cols }, () => new Array(cols).fill(undefined)));
5
6 const dfs = (r, c1, c2) => {
7 if (c1 < 0 || c1 >= cols || c2 < 0 || c2 >= cols) return 0;
8 if (r === rows) return 0;
9 if (memo[r][c1][c2] !== undefined) return memo[r][c1][c2];
10
11 let result = grid[r][c1];
12 if (c1 !== c2) result += grid[r][c2];
13
14 let max = 0;
15 for (let nc1 = c1 - 1; nc1 <= c1 + 1; nc1++) {
16 for (let nc2 = c2 - 1; nc2 <= c2 + 1; nc2++) {
17 max = Math.max(max, dfs(r + 1, nc1, nc2));
18 }
19 }
20 memo[r][c1][c2] = result + max;
21 return memo[r][c1][c2];
22 };
23
24 return dfs(0, 0, cols - 1);
25};The JavaScript solution also employs recursion with memoization. It uses an arrow function dfs to handle recursion, caching the results in the memo array. It tries potential moves for both robots, tracking maximum cherries collectable.