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
1public class Solution {
2 public int cherryPickup(int[][] grid) {
3 int rows = grid.length, cols = grid[0].length;
4 Integer[][][] memo = new Integer[rows][cols][cols];
5 return dfs(grid, 0, 0, cols - 1, memo);
6 }
7
8 private int dfs(int[][] grid, int r, int c1, int c2, Integer[][][] memo) {
9 if (c1 < 0 || c1 >= grid[0].length || c2 < 0 || c2 >= grid[0].length) return 0;
10 if (r == grid.length) return 0;
11 if (memo[r][c1][c2] != null) return memo[r][c1][c2];
12
13 int result = grid[r][c1];
14 if (c1 != c2) result += grid[r][c2];
15
16 int max = 0;
17 for (int nc1 = c1 - 1; nc1 <= c1 + 1; nc1++) {
18 for (int nc2 = c2 - 1; nc2 <= c2 + 1; nc2++) {
19 max = Math.max(max, dfs(grid, r + 1, nc1, nc2, memo));
20 }
21 }
22
23 memo[r][c1][c2] = result + max;
24 return memo[r][c1][c2];
25 }
26}The Java solution uses recursion with memoization, where dfs is the recursive function that calculates the maximum cherries possible from any given position, storing results in memo to optimize repeat calculations. Each call considers new positions for the robots in the next row.