Cherry Pickup
Problem
Given an n x n grid with cherries (1), empty cells (0), and thorns (-1), pick up as many cherries as possible by walking from top-left to bottom-right and back, only moving down/right then up/left. Return -1 if no valid round trip exists.
grid=[[0,1,-1],[1,0,-1],[1,1,1]]5def cherryPickup(grid):
n = len(grid)
memo = {}
def dp(r1, c1, r2):
c2 = r1 + c1 - r2
if r1 == n or c1 == n or r2 == n or c2 == n: return float('-inf')
if grid[r1][c1] == -1 or grid[r2][c2] == -1: return float('-inf')
if r1 == n - 1 and c1 == n - 1: return grid[r1][c1]
if (r1, c1, r2) in memo: return memo[(r1, c1, r2)]
cherries = grid[r1][c1] + (grid[r2][c2] if (r1, c1) != (r2, c2) else 0)
best = max(dp(r1+1, c1, r2+1), dp(r1+1, c1, r2), dp(r1, c1+1, r2+1), dp(r1, c1+1, r2))
memo[(r1, c1, r2)] = cherries + best
return memo[(r1, c1, r2)]
return max(0, dp(0, 0, 0))function cherryPickup(grid) {
const n = grid.length;
const memo = new Map();
function dp(r1, c1, r2) {
const c2 = r1 + c1 - r2;
if (r1 === n || c1 === n || r2 === n || c2 === n) return -Infinity;
if (grid[r1][c1] === -1 || grid[r2][c2] === -1) return -Infinity;
if (r1 === n - 1 && c1 === n - 1) return grid[r1][c1];
const key = r1 * n * n + c1 * n + r2;
if (memo.has(key)) return memo.get(key);
let cherries = grid[r1][c1] + (r1 === r2 && c1 === c2 ? 0 : grid[r2][c2]);
cherries += Math.max(dp(r1+1, c1, r2+1), dp(r1+1, c1, r2), dp(r1, c1+1, r2+1), dp(r1, c1+1, r2));
memo.set(key, cherries);
return cherries;
}
return Math.max(0, dp(0, 0, 0));
}class Solution {
int n; int[][][] memo; int[][] g;
public int cherryPickup(int[][] grid) {
n = grid.length; g = grid;
memo = new int[n][n][n];
for (int[][] a : memo) for (int[] b : a) Arrays.fill(b, Integer.MIN_VALUE);
return Math.max(0, dp(0, 0, 0));
}
int dp(int r1, int c1, int r2) {
int c2 = r1 + c1 - r2;
if (r1 == n || c1 == n || r2 == n || c2 == n) return Integer.MIN_VALUE / 2;
if (g[r1][c1] == -1 || g[r2][c2] == -1) return Integer.MIN_VALUE / 2;
if (r1 == n - 1 && c1 == n - 1) return g[r1][c1];
if (memo[r1][c1][r2] != Integer.MIN_VALUE) return memo[r1][c1][r2];
int cherries = g[r1][c1] + (r1 == r2 && c1 == c2 ? 0 : g[r2][c2]);
cherries += Math.max(Math.max(dp(r1+1, c1, r2+1), dp(r1+1, c1, r2)), Math.max(dp(r1, c1+1, r2+1), dp(r1, c1+1, r2)));
return memo[r1][c1][r2] = cherries;
}
}class Solution {
int n; vector<vector<vector<int>>> memo; vector<vector<int>>* g;
public:
int cherryPickup(vector<vector<int>>& grid) {
n = grid.size(); g = &grid;
memo.assign(n, vector<vector<int>>(n, vector<int>(n, INT_MIN)));
return max(0, dp(0, 0, 0));
}
int dp(int r1, int c1, int r2) {
int c2 = r1 + c1 - r2;
if (r1 == n || c1 == n || r2 == n || c2 == n) return INT_MIN / 2;
if ((*g)[r1][c1] == -1 || (*g)[r2][c2] == -1) return INT_MIN / 2;
if (r1 == n - 1 && c1 == n - 1) return (*g)[r1][c1];
if (memo[r1][c1][r2] != INT_MIN) return memo[r1][c1][r2];
int cherries = (*g)[r1][c1] + (r1 == r2 && c1 == c2 ? 0 : (*g)[r2][c2]);
cherries += max({dp(r1+1, c1, r2+1), dp(r1+1, c1, r2), dp(r1, c1+1, r2+1), dp(r1, c1+1, r2)});
return memo[r1][c1][r2] = cherries;
}
};Explanation
The big trick is realizing that a trip there and back is the same as two trips going only down and right at the same time. So instead of one walker going forward then backward, we send two walkers from the top-left simultaneously and let them choose the best columns.
Both walkers take the same number of steps, so after step moves a walker at row r must be at column step - r. That means once we know r1, c1 and r2, the fourth value c2 = r1 + c1 - r2 is forced — we only need three coordinates in the state.
At each state we collect grid[r1][c1] plus grid[r2][c2], but if both walkers stand on the same cell we count that cherry only once. We then try all 4 combinations of "each walker moves down or right" and keep the best, caching results in memo.
A cell with -1 is a thorn and returns negative infinity so that path is never chosen. At the very end we return max(0, dp(0,0,0)) so an impossible trip yields 0 (the wrapper treats it as no cherries).
Example: grid=[[0,1,-1],[1,0,-1],[1,1,1]]. The two coordinated walks together pick up 5 cherries.