Log inSign up
hardLeetCodeNot Started

Cherry Pickup II

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

Dynamic Programming
Solve on LeetCode
Lesson

Problem Statement

You are given a rows x cols matrix grid representing a field of cherries where grid[i][j] represents the number of cherries that you can collect from the (i, j) cell.

You have two robots that can collect cherries for you: Robot #1 is located at the top-left corner (0, 0), and Robot #2 is located at the top-right corner (0, cols - 1).

Return the maximum number of cherries collection using both robots by following the rules below: - From a cell (i, j), robots can move to cell (i + 1, j - 1), (i + 1, j), or (i + 1, j + 1). - When any robot passes through a cell, it picks up all cherries, and the cell becomes empty. - When both robots stay in the same cell at the same time, only one takes the cherries. - Both robots must reach the bottom row in grid.

### Example 1 - Input: ``text grid = [ [3, 1, 1], [2, 5, 1], [1, 5, 5], [2, 1, 1] ] ` - **Output**: 24 - **Explanation**: Path of robot #1: 3 -> 2 -> 5 -> 2. Path of robot #2: 1 -> 5 -> 5 -> 1. Total cherries = 12 + 12 = 24`.

### Example 2 - Input: ``text grid = [ [1, 0, 0, 0, 0, 0, 1], [2, 0, 0, 0, 0, 3, 0], [2, 0, 9, 0, 0, 0, 0], [0, 3, 0, 5, 4, 0, 0], [1, 0, 2, 3, 0, 0, 6] ] ` - **Output**: 28`

Constraints:

  • rows == grid.length
  • cols == grid[i].length
  • 2 <= rows, cols <= 70
  • 0 <= grid[i][j] <= 100

What You'll Learn

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

  • Exploit synchronous row progression to reduce state dimensions.
  • Formulate multi-agent 9-direction transitions.
  • Space-optimize 3D DP table into 2D rolling matrix.

Pattern Recognition Trigger

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

Signals to Look For:

  • Two agents moving simultaneously down a grid row-by-row.
  • Shared resource collision resolution (only 1 picks cherries).

Algorithmic Decision Tree:

  • Iterate row backwards from rows - 1 down to 0.
  • Check column boundaries 0 <= c1, c2 < cols.

Connected Patterns:

Cherry PickupMinimum Falling Path SumTriangle Minimum Path Sum

1. Recursive 9-Way Branching

Intuition

Recursively explore all 3 moves for robot 1 and 3 moves for robot 2 at each row.

Algorithm

  1. Define solve(r, c1, c2).
  2. If c1 < 0 || c1 >= cols || c2 < 0 || c2 >= cols, return -\infty.
  3. Cherries = (c1 == c2) ? grid[r][c1] : grid[r][c1] + grid[r][c2].
  4. If r == rows - 1, return cherries.
  5. Try all 9 combinations: dc1 in {-1, 0, 1}, dc2 in {-1, 0, 1}.
  6. Return cherries + max(all 9 next states).
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7class Solution {
8 int solve(int r, int c1, int c2, int rows, int cols, const vector<vector<int>>& grid) {
9 if (c1 < 0 || c1 >= cols || c2 < 0 || c2 >= cols) return -1e9;
10
11 int cherries = (c1 == c2) ? grid[r][c1] : grid[r][c1] + grid[r][c2];
12 if (r == rows - 1) return cherries;
13
14 int maxNext = -1e9;
15 for (int dc1 = -1; dc1 <= 1; ++dc1) {
16 for (int dc2 = -1; dc2 <= 1; ++dc2) {
17 maxNext = max(maxNext, solve(r + 1, c1 + dc1, c2 + dc2, rows, cols, grid));
18 }
19 }
20
21 return cherries + maxNext;
22 }
23public:
24 int cherryPickup(vector<vector<int>>& grid) {
25 return solve(0, 0, grid[0].size() - 1, grid.size(), grid[0].size(), grid);
26 }
27};
28
29int main() {
30 Solution sol;
31 vector<vector<int>> grid = {{3, 1, 1}, {2, 5, 1}, {1, 5, 5}, {2, 1, 1}};
32 cout << "Max Cherries: " << sol.cherryPickup(grid) << endl;
33 return 0;
34}

Time & Space Complexity

  • Time complexity: O(9^rows)
  • Space complexity: O(rows) call stack

2. Memoized 3D Top-Down DP

Intuition

Store intermediate results for (r, c1, c2) in a 3D table memo[rows][cols][cols].

Algorithm

  1. Initialize memo[rows][cols][cols] with -1.
  2. In solve(r, c1, c2): return memo[r][c1][c2] if != -1.
  3. Evaluate all 9 transitions.
  4. Store 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 r, int c1, int c2, int rows, int cols, const vector<vector<int>>& grid, vector<vector<vector<int>>>& memo) {
9 if (c1 < 0 || c1 >= cols || c2 < 0 || c2 >= cols) return -1e9;
10 if (memo[r][c1][c2] != -1) return memo[r][c1][c2];
11
12 int cherries = (c1 == c2) ? grid[r][c1] : grid[r][c1] + grid[r][c2];
13 if (r == rows - 1) return memo[r][c1][c2] = cherries;
14
15 int maxNext = -1e9;
16 for (int dc1 = -1; dc1 <= 1; ++dc1) {
17 for (int dc2 = -1; dc2 <= 1; ++dc2) {
18 maxNext = max(maxNext, solve(r + 1, c1 + dc1, c2 + dc2, rows, cols, grid, memo));
19 }
20 }
21
22 return memo[r][c1][c2] = cherries + maxNext;
23 }
24public:
25 int cherryPickup(vector<vector<int>>& grid) {
26 int rows = grid.size(), cols = grid[0].size();
27 vector<vector<vector<int>>> memo(rows, vector<vector<int>>(cols, vector<int>(cols, -1)));
28 return solve(0, 0, cols - 1, rows, cols, grid, memo);
29 }
30};
31
32int main() {
33 Solution sol;
34 vector<vector<int>> grid = {{3, 1, 1}, {2, 5, 1}, {1, 5, 5}, {2, 1, 1}};
35 cout << "Max Cherries: " << sol.cherryPickup(grid) << endl;
36 return 0;
37}

Time & Space Complexity

  • Time complexity: O(rows * cols^2 * 9)
  • Space complexity: O(rows * cols^2)

3. Space-Optimized 2D Bottom-Up Tabulation

Intuition

Iterate bottom-up from rows - 1 down to 0, maintaining only a 2D matrix dp[cols][cols].

Algorithm

  1. Initialize dp[cols][cols] for the base row rows - 1.
  2. For row r from rows - 2 down to 0:
  3. Initialize nextDp[cols][cols] with 0.
  4. For c1 from 0 to cols - 1:
  5. For c2 from 0 to cols - 1:
  6. cherries = (c1 == c2) ? grid[r][c1] : grid[r][c1] + grid[r][c2].
  7. maxNext = 0.
  8. For dc1 in {-1, 0, 1} and dc2 in {-1, 0, 1}:
  9. nc1 = c1 + dc1, nc2 = c2 + dc2.
  10. If in bounds, maxNext = max(maxNext, dp[nc1][nc2]).
  11. nextDp[c1][c2] = cherries + maxNext.
  12. dp = nextDp.
  13. Return dp[0][cols - 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 rows = grid.size(), cols = grid[0].size();
11 vector<vector<int>> dp(cols, vector<int>(cols, 0));
12
13 // Base case: row = rows - 1
14 for (int c1 = 0; c1 < cols; ++c1) {
15 for (int c2 = 0; c2 < cols; ++c2) {
16 dp[c1][c2] = (c1 == c2) ? grid[rows - 1][c1] : grid[rows - 1][c1] + grid[rows - 1][c2];
17 }
18 }
19
20 // Bottom-up row by row
21 for (int r = rows - 2; r >= 0; --r) {
22 vector<vector<int>> nextDp(cols, vector<int>(cols, 0));
23 for (int c1 = 0; c1 < cols; ++c1) {
24 for (int c2 = 0; c2 < cols; ++c2) {
25 int cherries = (c1 == c2) ? grid[r][c1] : grid[r][c1] + grid[r][c2];
26 int maxNext = 0;
27
28 for (int dc1 = -1; dc1 <= 1; ++dc1) {
29 for (int dc2 = -1; dc2 <= 1; ++dc2) {
30 int nc1 = c1 + dc1, nc2 = c2 + dc2;
31 if (nc1 >= 0 && nc1 < cols && nc2 >= 0 && nc2 < cols) {
32 maxNext = max(maxNext, dp[nc1][nc2]);
33 }
34 }
35 }
36
37 nextDp[c1][c2] = cherries + maxNext;
38 }
39 }
40 dp = move(nextDp);
41 }
42
43 return dp[0][cols - 1];
44 }
45};
46
47int main() {
48 Solution sol;
49 vector<vector<int>> grid = {{3, 1, 1}, {2, 5, 1}, {1, 5, 5}, {2, 1, 1}};
50 cout << "Max Cherries: " << sol.cherryPickup(grid) << endl;
51 return 0;
52}

Time & Space Complexity

  • Time complexity: O(rows * cols^2 * 9)
  • Space complexity: O(cols^2)

Approach Comparison Matrix

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

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Recursive 9-Way SearchO(9^rows)O(rows)Exhaustive branching over all 9 dual-robot move combinations.Overlapping subproblems
2.Memoized 3D DPO(rows * cols^2 * 9)O(rows * cols^2)Cache states in 3D memo table.Table allocation
3.Space-Optimized 2D TabulationOptimalO(rows * cols^2 * 9)O(cols^2)Iteratively collapse rows upwards into a 2D matrix.None

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Adding cherries twice when both robots occupy the same column.

Pitfall 2:

Missing boundary checks when checking c1 + dc1 or c2 + dc2.

Crucial Edge Cases to Validate:

  • Robots cross paths (c1 == c2): Cherries added only once.
  • cols = 2: Both robots start adjacent at (0, 0) and (0, 1).

Interview Tips & Best Practices

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

  1. Emphasize why row r is identical for both robots: both robots must advance exactly one row at every step, making a 3D state (r, c1, c2) completely sufficient.

Quick Comprehension Check

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

1.Why do we evaluate 9 possible next positions at each row step in Cherry Pickup II?

Back to DSA Sheet