Cherry Pickup

Hard · 1-D Dynamic Programming · Explanation and code example

Dynamic Programming (Space Optimized)

How it works

Since we process states by the total number of steps k = r1 + c1 = r2 + c2, and each state only depends on states from the previous step count, we only need to keep track of the previous layer. This reduces space from O(n^3) to O(n^2) by using two 2D arrays that alternate between the current and previous step.

Steps

  1. Create a 2D prev array of size [n][n] representing states for the previous step count.
  2. Initialize prev[0][0] with the starting cell's cherry value.
  3. For each step count k from 1 to 2n-2:
    • Create a new 2D dp array for the current step.
    • For each valid (r1, r2) pair where c1 = k - r1 and c2 = k - r2 are within bounds:
      • Look at all 4 transitions from the previous step.
      • Take the maximum and add current cherries (avoiding double counting).
    • Set prev = dp for the next iteration.
  4. Return prev[n-1][n-1], clamped to 0 if negative.

Complexity

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

Things to watch for

Solving as Two Independent Paths

Running a greedy or DP solution for the forward path, removing collected cherries, then solving the return path separately. This approach fails because the optimal combined solution may require a suboptimal forward path to enable a better return path. Both paths must be considered simultaneously.

Double Counting Cherries When Paths Overlap

Forgetting to subtract cherries when both simulated people land on the same cell. If (r1, c1) == (r2, c2), you must count cherries only once.

Ignoring Blocked Cells (-1) Properly

Returning 0 instead of a large negative value when hitting a thorn. Returning 0 makes invalid paths appear viable when taking the maximum. Return -1000 or float('-inf') to ensure invalid paths are never selected.

Forgetting to Handle No Valid Path

Not checking if the final result is negative before returning. If no valid path exists (blocked by thorns), the algorithm may return a negative number. The answer should be max(0, result).

Using 4D State Without Optimization

Not recognizing that c2 can be derived from c1, r1, and r2 since both people take the same number of steps (r1 + c1 == r2 + c2). This optimization reduces state space from O(n^4) to O(n^3).

Python code example

from typing import List

class Solution:
    def cherryPickup(self, grid: List[List[int]]) -> int:
        n = len(grid)
        prev = [[float("-inf")] * n for _ in range(n)]
        prev[0][0] = grid[0][0]

        for k in range(1, 2 * n - 1):
            dp = [[float("-inf")] * n for _ in range(n)]
            for r1 in range(max(0, k - (n - 1)), min(n, k + 1)):
                c1 = k - r1
                if c1 >= n or grid[r1][c1] == -1:
                    continue
                for r2 in range(max(0, k - (n - 1)), min(n, k + 1)):
                    c2 = k - r2
                    if c2 >= n or grid[r2][c2] == -1:
                        continue
                    val = prev[r1][r2]
                    if r1 > 0: val = max(val, prev[r1 - 1][r2])
                    if r2 > 0: val = max(val, prev[r1][r2 - 1])
                    if r1 > 0 and r2 > 0: val = max(val, prev[r1 - 1][r2 - 1])
                    if val < 0: continue
                    val += grid[r1][c1]
                    if r1 != r2: val += grid[r2][c2]
                    dp[r1][r2] = val
            prev = dp

        return max(0, prev[n - 1][n - 1])

C++ code example

class Solution {
public:
    int cherryPickup(vector<vector<int>>& grid) {
        int n = grid.size();
        vector<vector<int>> prev(n, vector<int>(n, INT_MIN));
        prev[0][0] = grid[0][0];

        for (int k = 1; k < 2 * n - 1; k++) {
            vector<vector<int>> dp(n, vector<int>(n, INT_MIN));
            for (int r1 = max(0, k - (n - 1)); r1 <= min(n - 1, k); r1++) {
                int c1 = k - r1;
                if (c1 >= n || grid[r1][c1] == -1) continue;
                for (int r2 = max(0, k - (n - 1)); r2 <= min(n - 1, k); r2++) {
                    int c2 = k - r2;
                    if (c2 >= n || grid[r2][c2] == -1) continue;
                    int val = prev[r1][r2];
                    if (r1 > 0) val = max(val, prev[r1 - 1][r2]);
                    if (r2 > 0) val = max(val, prev[r1][r2 - 1]);
                    if (r1 > 0 && r2 > 0) val = max(val, prev[r1 - 1][r2 - 1]);
                    if (val < 0) continue;
                    val += grid[r1][c1];
                    if (r1 != r2) val += grid[r2][c2];
                    dp[r1][r2] = val;
                }
            }
            prev = dp;
        }

        return max(0, prev[n - 1][n - 1]);
    }
};
Source and license

Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.

Check the explanation on LeetCode

Your recall check is in progress. Write your attempt before revealing the explanation.

Resume recall check

Browse all problem explanations