741. Cherry Pickup
Problem Description
You are given an n x n grid representing a field of cherries, each cell is one of three possible integers:
- 0 means the cell is empty, so you can pass through it
- 1 means the cell contains a cherry that you can pick up and pass through it
- -1 means the cell contains a thorn that blocks your way
Return the maximum number of cherries you can collect by following the rules below:
- Starting at the position (0, 0) and reaching (n-1, n-1) by moving right or down through valid path cells (cells with value 0 or 1)
- After reaching (n-1, n-1), returning to (0, 0) by moving left or up through valid path cells
- When passing through a path cell containing a cherry, you pick it up and the cell becomes an empty cell (0)
- If there is no valid path between (0, 0) and (n-1, n-1), then no cherries can be collected
Examples:
Example 1:
Input: grid = [[0,1,-1],[1,0,-1],[1,1,1]] Output: 5 Explanation: The player started at (0, 0) and went down, down, right right to reach (2, 2). 4 cherries were picked up during this single trip, and the matrix becomes [[0,1,-1],[0,0,-1],[0,0,0]]. Then, the player went left, up, up, left to return home, picking up one more cherry. The total number of cherries picked up is 5, and we can prove this is the maximum possible.
Example 2:
Input: grid = [[1,1,-1],[1,-1,1],[-1,1,1]] Output: 0
Constraints:
- n == grid.length
- n == grid[i].length
- 2 ≤ n ≤ 50
- grid[i][j] is -1, 0, or 1
- grid[0][0] != -1
- grid[n-1][n-1] != -1
Python Solution
class Solution:
def cherryPickup(self, grid: List[List[int]]) -> int:
n = len(grid)
memo = {}
def dp(r1, c1, r2, c2):
# If either person goes out of bounds or hits a thorn
if (r1 >= n or c1 >= n or r2 >= n or c2 >= n or
grid[r1][c1] == -1 or grid[r2][c2] == -1):
return float('-inf')
# If both reach the end
if r1 == n-1 and c1 == n-1 and r2 == n-1 and c2 == n-1:
return grid[r1][c1]
# If already calculated
if (r1, c1, r2, c2) in memo:
return memo[(r1, c1, r2, c2)]
# Calculate cherries picked up
cherries = grid[r1][c1]
if r1 != r2 or c1 != c2:
cherries += grid[r2][c2]
# Try all possible moves
cherries += max(
dp(r1+1, c1, r2+1, c2), # both down
dp(r1+1, c1, r2, c2+1), # first down, second right
dp(r1, c1+1, r2+1, c2), # first right, second down
dp(r1, c1+1, r2, c2+1) # both right
)
memo[(r1, c1, r2, c2)] = cherries
return cherries
result = dp(0, 0, 0, 0)
return max(0, result)Implementation Notes:
- Uses dynamic programming with memoization to solve the problem
- Simulates two people moving simultaneously to avoid picking up the same cherry twice
- Time complexity: O(n^4) where n is the grid size
- Space complexity: O(n^4) for the memoization cache
Java Solution
class Solution {
private int n;
private int[][] grid;
private Map memo;
public int cherryPickup(int[][] grid) {
this.grid = grid;
this.n = grid.length;
this.memo = new HashMap<>();
int result = dp(0, 0, 0, 0);
return Math.max(0, result);
}
private int dp(int r1, int c1, int r2, int c2) {
// If either person goes out of bounds or hits a thorn
if (r1 >= n || c1 >= n || r2 >= n || c2 >= n ||
grid[r1][c1] == -1 || grid[r2][c2] == -1) {
return Integer.MIN_VALUE;
}
// If both reach the end
if (r1 == n-1 && c1 == n-1 && r2 == n-1 && c2 == n-1) {
return grid[r1][c1];
}
// If already calculated
String key = r1 + "," + c1 + "," + r2 + "," + c2;
if (memo.containsKey(key)) {
return memo.get(key);
}
// Calculate cherries picked up
int cherries = grid[r1][c1];
if (r1 != r2 || c1 != c2) {
cherries += grid[r2][c2];
}
// Try all possible moves
cherries += Math.max(
Math.max(dp(r1+1, c1, r2+1, c2), dp(r1+1, c1, r2, c2+1)),
Math.max(dp(r1, c1+1, r2+1, c2), dp(r1, c1+1, r2, c2+1))
);
memo.put(key, cherries);
return cherries;
}
} C++ Solution
class Solution {
private:
int n;
vector> grid;
map memo;
int dp(int r1, int c1, int r2, int c2) {
// If either person goes out of bounds or hits a thorn
if (r1 >= n || c1 >= n || r2 >= n || c2 >= n ||
grid[r1][c1] == -1 || grid[r2][c2] == -1) {
return INT_MIN;
}
// If both reach the end
if (r1 == n-1 && c1 == n-1 && r2 == n-1 && c2 == n-1) {
return grid[r1][c1];
}
// If already calculated
string key = to_string(r1) + "," + to_string(c1) + "," +
to_string(r2) + "," + to_string(c2);
if (memo.count(key)) {
return memo[key];
}
// Calculate cherries picked up
int cherries = grid[r1][c1];
if (r1 != r2 || c1 != c2) {
cherries += grid[r2][c2];
}
// Try all possible moves
cherries += max({
dp(r1+1, c1, r2+1, c2),
dp(r1+1, c1, r2, c2+1),
dp(r1, c1+1, r2+1, c2),
dp(r1, c1+1, r2, c2+1)
});
memo[key] = cherries;
return cherries;
}
public:
int cherryPickup(vector>& grid) {
this->grid = grid;
this->n = grid.size();
int result = dp(0, 0, 0, 0);
return max(0, result);
}
}; JavaScript Solution
function cherryPickup(grid) {
const n = grid.length;
const memo = new Map();
function dp(r1, c1, r2, c2) {
// If either person goes out of bounds or hits a thorn
if (r1 >= n || c1 >= n || r2 >= n || c2 >= n ||
grid[r1][c1] === -1 || grid[r2][c2] === -1) {
return -Infinity;
}
// If both reach the end
if (r1 === n-1 && c1 === n-1 && r2 === n-1 && c2 === n-1) {
return grid[r1][c1];
}
// If already calculated
const key = `${r1},${c1},${r2},${c2}`;
if (memo.has(key)) {
return memo.get(key);
}
// Calculate cherries picked up
let cherries = grid[r1][c1];
if (r1 !== r2 || c1 !== c2) {
cherries += grid[r2][c2];
}
// Try all possible moves
cherries += Math.max(
dp(r1+1, c1, r2+1, c2),
dp(r1+1, c1, r2, c2+1),
dp(r1, c1+1, r2+1, c2),
dp(r1, c1+1, r2, c2+1)
);
memo.set(key, cherries);
return cherries;
}
const result = dp(0, 0, 0, 0);
return Math.max(0, result);
}C# Solution
public class Solution {
private int n;
private int[][] grid;
private Dictionary memo;
public int CherryPickup(int[][] grid) {
this.grid = grid;
this.n = grid.Length;
this.memo = new Dictionary();
int result = Dp(0, 0, 0, 0);
return Math.Max(0, result);
}
private int Dp(int r1, int c1, int r2, int c2) {
// If either person goes out of bounds or hits a thorn
if (r1 >= n || c1 >= n || r2 >= n || c2 >= n ||
grid[r1][c1] == -1 || grid[r2][c2] == -1) {
return int.MinValue;
}
// If both reach the end
if (r1 == n-1 && c1 == n-1 && r2 == n-1 && c2 == n-1) {
return grid[r1][c1];
}
// If already calculated
string key = $"{r1},{c1},{r2},{c2}";
if (memo.ContainsKey(key)) {
return memo[key];
}
// Calculate cherries picked up
int cherries = grid[r1][c1];
if (r1 != r2 || c1 != c2) {
cherries += grid[r2][c2];
}
// Try all possible moves
cherries += Math.Max(
Math.Max(Dp(r1+1, c1, r2+1, c2), Dp(r1+1, c1, r2, c2+1)),
Math.Max(Dp(r1, c1+1, r2+1, c2), Dp(r1, c1+1, r2, c2+1))
);
memo[key] = cherries;
return cherries;
}
} Implementation Notes:
- Uses dynamic programming with memoization to solve the problem
- Simulates two people moving simultaneously to avoid picking up the same cherry twice
- Time complexity: O(n^4) where n is the grid size
- Space complexity: O(n^4) for the memoization cache