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)
1#include <vector>
2#include <algorithm>
3using namespace std;
4
5int cherryPickup(vector<vector<int>>& grid) {
6 int rows = grid.size(), cols = grid[0].size();
7 vector<vector<vector<int>>> dp(rows, vector<vector<int>>(cols, vector<int>(cols, 0)));
8 for (int r = rows - 1; r >= 0; r--) {
9 for (int c1 = 0; c1 < cols; c1++) {
10 for (int c2 = 0; c2 < cols; c2++) {
11 int max_cherries = 0;
12 for (int newC1 = c1 - 1; newC1 <= c1 + 1; newC1++) {
13 for (int newC2 = c2 - 1; newC2 <= c2 + 1; newC2++) {
14 if (newC1 >= 0 && newC1 < cols && newC2 >= 0 && newC2 < cols)
15 max_cherries = max(max_cherries, (r + 1 < rows ? dp[r + 1][newC1][newC2] : 0));
16 }
17 }
18 dp[r][c1][c2] = grid[r][c1] + (c1 == c2 ? 0 : grid[r][c2]) + max_cherries;
19 }
20 }
21 }
22 return dp[0][0][cols - 1];
23}The solution follows the same logic as the Python version. We use a 3D vector dp to store the maximum cherries collectable with robots starting at different positions in each row, transitioning from the bottom up, ensuring the optimal movements for both robots are considered.
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.