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
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.