Log inSign up
hardLeetCodeNot Started

Cherry Pickup

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Dynamic Programming
Solve on LeetCode
Lesson

Problem Statement

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. - 1 means the cell contains a cherry that you can pick up and pass through. - -1 means the cell contains a thorn that blocks your way.

Return the maximum number of cherries you can collect by following these rules: 1. Starting at (0, 0) and reaching (n - 1, n - 1) by moving only right or down through valid cells. 2. After reaching (n - 1, n - 1), returning to (0, 0) by moving only left or up through valid cells. 3. When passing through a cell with a cherry, you pick it up, and the cell becomes empty (0). 4. If there is no valid path between (0, 0) and (n - 1, n - 1), then no cherries can be collected.

### Example 1 - Input: grid = [[0, 1, -1], [1, 0, -1], [1, 1, 1]] - Output: 5 - Explanation: The player started at (0, 0) and went to (2, 2) collecting 3 cherries, then returned to (0, 0) collecting 2 cherries.

### Example 2 - Input: grid = [[1, 1, -1], [1, -1, 1], [-1, 1, 1]] - Output: 0

Constraints:

  • n == grid.length == grid[i].length
  • 1 <= n <= 50
  • grid[i][j] is -1, 0, or 1
  • grid[0][0] != -1 and grid[n - 1][n - 1] != -1

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Transform round-trip path problems into dual forward traversals.
  • Eliminate a state dimension via Manhattan distance conservation.
  • Prevent double-counting when multiple paths intersect.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Round-trip on grid with items consumed along the way.
  • Greedy on first pass fails because first path choice affects the return path.

Algorithmic Decision Tree:

  • Model both paths simultaneously.
  • Use step constraint to eliminate 4th dimension.

Connected Patterns:

Cherry Pickup IIMinimum Path SumChomp Game

1. Recursive Dual DFS

Intuition

Recursively advance both travelers right or down simultaneously through all 4 branches.

Algorithm

  1. Define solve(r1, c1, r2).
  2. c2 = r1 + c1 - r2.
  3. If out of bounds or thorn (-1) at either position, return -\infty.
  4. If both reach (n-1, n-1), return grid[n-1][n-1].
  5. Cherries gained = (r1 == r2) ? grid[r1][c1] : grid[r1][c1] + grid[r2][c2].
  6. Branch 4 ways: (r1+1, c1, r2+1), (r1+1, c1, r2), (r1, c1+1, r2+1), (r1, c1+1, r2).
  7. Return cherries + max(all 4 branches).
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7class Solution {
8 int solve(int r1, int c1, int r2, int n, const vector<vector<int>>& grid) {
9 int c2 = r1 + c1 - r2;
10 if (r1 >= n || c1 >= n || r2 >= n || c2 >= n || grid[r1][c1] == -1 || grid[r2][c2] == -1) {
11 return -1e9;
12 }
13 if (r1 == n - 1 && c1 == n - 1) return grid[r1][c1];
14
15 int cherries = (r1 == r2) ? grid[r1][c1] : grid[r1][c1] + grid[r2][c2];
16
17 int bestNext = max({
18 solve(r1 + 1, c1, r2 + 1, n, grid), // Down, Down
19 solve(r1 + 1, c1, r2, n, grid), // Down, Right
20 solve(r1, c1 + 1, r2 + 1, n, grid), // Right, Down
21 solve(r1, c1 + 1, r2, n, grid) // Right, Right
22 });
23
24 return cherries + bestNext;
25 }
26public:
27 int cherryPickup(vector<vector<int>>& grid) {
28 int ans = solve(0, 0, 0, grid.size(), grid);
29 return max(0, ans);
30 }
31};
32
33int main() {
34 Solution sol;
35 vector<vector<int>> grid = {{0, 1, -1}, {1, 0, -1}, {1, 1, 1}};
36 cout << "Max Cherries: " << sol.cherryPickup(grid) << endl;
37 return 0;
38}

Time & Space Complexity

  • Time complexity: O(4^(2n))
  • Space complexity: O(n) call stack

2. Memoized 3D Top-Down DP

Intuition

Memoize states in a 3D table memo[n][n][n] indexed by (r1, c1, r2).

Algorithm

  1. Initialize memo[n][n][n] with -2.
  2. In solve(r1, c1, r2): return memo[r1][c1][r2] if != -2.
  3. Compute cherries and 4 branch transitions.
  4. Save in memo table and return.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7class Solution {
8 int solve(int r1, int c1, int r2, int n, const vector<vector<int>>& grid, vector<vector<vector<int>>>& memo) {
9 int c2 = r1 + c1 - r2;
10 if (r1 >= n || c1 >= n || r2 >= n || c2 >= n || grid[r1][c1] == -1 || grid[r2][c2] == -1) {
11 return -1e9;
12 }
13 if (r1 == n - 1 && c1 == n - 1) return grid[r1][c1];
14 if (memo[r1][c1][r2] != -2) return memo[r1][c1][r2];
15
16 int cherries = (r1 == r2) ? grid[r1][c1] : grid[r1][c1] + grid[r2][c2];
17
18 int bestNext = max({
19 solve(r1 + 1, c1, r2 + 1, n, grid, memo),
20 solve(r1 + 1, c1, r2, n, grid, memo),
21 solve(r1, c1 + 1, r2 + 1, n, grid, memo),
22 solve(r1, c1 + 1, r2, n, grid, memo)
23 });
24
25 return memo[r1][c1][r2] = cherries + bestNext;
26 }
27public:
28 int cherryPickup(vector<vector<int>>& grid) {
29 int n = grid.size();
30 vector<vector<vector<int>>> memo(n, vector<vector<int>>(n, vector<int>(n, -2)));
31 int ans = solve(0, 0, 0, n, grid, memo);
32 return max(0, ans);
33 }
34};
35
36int main() {
37 Solution sol;
38 vector<vector<int>> grid = {{0, 1, -1}, {1, 0, -1}, {1, 1, 1}};
39 cout << "Max Cherries: " << sol.cherryPickup(grid) << endl;
40 return 0;
41}

Time & Space Complexity

  • Time complexity: O(n^3)
  • Space complexity: O(n^3)

3. Step-Based 2D Space-Optimized Tabulation

Intuition

Iterate by step count k = r1 + c1 from 0 to 2n - 2. Keep only a 2D matrix dp[r1][r2] representing max cherries for the current step.

Algorithm

  1. Initialize dp[n][n] with -1; dp[0][0] = grid[0][0].
  2. Loop k from 1 to 2n - 2:
  3. Initialize nextDp[n][n] with -1.
  4. For r1 from max(0, k - (n - 1)) to min(n - 1, k):
  5. c1 = k - r1.
  6. For r2 from max(0, k - (n - 1)) to min(n - 1, k):
  7. c2 = k - r2.
  8. If grid[r1][c1] == -1 || grid[r2][c2] == -1, continue.
  9. Find max previous state from (r1, r2), (r1-1, r2), (r1, r2-1), (r1-1, r2-1).
  10. If valid, nextDp[r1][r2] = maxPrev + cherries.
  11. dp = nextDp.
  12. Return max(0, dp[n - 1][n - 1]).
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7class Solution {
8public:
9 int cherryPickup(vector<vector<int>>& grid) {
10 int n = grid.size();
11 vector<vector<int>> dp(n, vector<int>(n, -1));
12 dp[0][0] = grid[0][0];
13
14 for (int k = 1; k <= 2 * n - 2; ++k) {
15 vector<vector<int>> nextDp(n, vector<int>(n, -1));
16 for (int r1 = max(0, k - (n - 1)); r1 <= min(n - 1, k); ++r1) {
17 int c1 = k - r1;
18 for (int r2 = max(0, k - (n - 1)); r2 <= min(n - 1, k); ++r2) {
19 int c2 = k - r2;
20 if (grid[r1][c1] == -1 || grid[r2][c2] == -1) continue;
21
22 int maxPrev = -1;
23 if (r1 > 0 && r2 > 0) maxPrev = max(maxPrev, dp[r1 - 1][r2 - 1]);
24 if (r1 > 0 && c2 > 0) maxPrev = max(maxPrev, dp[r1 - 1][r2]);
25 if (c1 > 0 && r2 > 0) maxPrev = max(maxPrev, dp[r1][r2 - 1]);
26 if (c1 > 0 && c2 > 0) maxPrev = max(maxPrev, dp[r1][r2]);
27
28 if (maxPrev < 0) continue;
29
30 int cherries = (r1 == r2) ? grid[r1][c1] : grid[r1][c1] + grid[r2][c2];
31 nextDp[r1][r2] = maxPrev + cherries;
32 }
33 }
34 dp = move(nextDp);
35 }
36
37 return max(0, dp[n - 1][n - 1]);
38 }
39};
40
41int main() {
42 Solution sol;
43 vector<vector<int>> grid = {{0, 1, -1}, {1, 0, -1}, {1, 1, 1}};
44 cout << "Max Cherries: " << sol.cherryPickup(grid) << endl;
45 return 0;
46}

Time & Space Complexity

  • Time complexity: O(n^3)
  • Space complexity: O(n^2)

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Recursive Dual DFSO(4^(2n))O(n)Exhaustive branching over 4 dual moves.Subproblem overlap
2.Memoized 3D DPO(n^3)O(n^3)Cache states in 3D memo table.Table allocation
3.Step-Based 2D Space-Optimized TabulationOptimalO(n^3)O(n^2)Collapse 3D state into 2D rolling matrix per step k.None

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Adding cherries twice when r1 == r2 and c1 == c2.

Pitfall 2:

Using 4 state variables (r1, c1, r2, c2) instead of expressing c2 = r1 + c1 - r2.

Crucial Edge Cases to Validate:

  • No path exists: Start or end blocked by -1 or walled off; returns 0.
  • 1x1 grid: Returns grid[0][0].
  • Both travelers on the same cell: Cherries added only once.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Immediately explain the transformation: 'A round trip from A to B and back to A is equivalent to two people walking simultaneously from A to B.' This shows top-tier algorithmic problem solving.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why does running two separate greedy passes (one down, one up) FAIL to find the optimal solution?

Back to DSA Sheet