DP 13: Cherry Pickup II | 3D Dynamic Programming on Grids

Welcome to the final chapter on Dynamic Programming on Grids. Having covered the foundational and advanced techniques across the previous twelve chapters, you are now equipped to tackle any grid-based dynamic programming problem. This chapter introduces 3D Dynamic Programming via the classic "Cherry Pickup II" problem. While the terminology sounds intimidating, the transition from 2D to 3D DP is conceptually straightforward once we map out the state variables and simultaneous paths.

1. The Problem Statement: Ninja, Alice, and Bob

Ninja has a 2D grid of size $R \times C$. Every cell in the grid contains a non-negative number of chocolates. Ninja has two friends, Alice and Bob, and wants to collect the maximum number of chocolates possible from the grid using both friends according to strict starting and moving rules:

• Starting Positions:
  • Alice always starts at the top-left corner: (0, 0).
  • Bob always starts at the top-right corner: (0, C - 1).
• Movement Rules:
  • From any cell (i, j), both Alice and Bob can move simultaneously downward to the next row in one of three diagonal directions:
    1. Down-Left: (i + 1, j - 1)
    2. Down-Straight: (i + 1, j)
    3. Down-Right: (i + 1, j + 1)
• Chocolate Collection Rules:
  • When a friend passes through a cell, they pick up all the chocolates in it, setting the cell's chocolate count to 0.
  • The Overlap Rule: If Alice and Bob land on the exact same cell at the same time, the chocolates in that cell are collected only once (they cannot double-dip).
• Goal: Find the maximum total number of chocolates Alice and Bob can collect together by the time they reach the last row.

2. Why Greedy Fails (The Non-Uniformity Trap)

Can we use a greedy approach—for instance, making Alice always pick the cell with the maximum chocolates and Bob do the same independently?

Note: Greedy fails completely in grid DP problems with non-uniform values. If a local choice yields immediate high rewards but traps the actor in a barren region for all subsequent rows, the overall sum will be suboptimal. Because future paths depend entirely on current positioning, we must evaluate all possible paths for both Alice and Bob concurrently to guarantee an optimal global maximum.

3. Why Separate Individual Paths Do Not Work

You might wonder: Why not run a standard 2D DP for Alice to find her best path, run a separate 2D DP for Bob to find his best path, and then sum the results?

• The Overlap Problem: If Alice and Bob pass through the exact same cell at some point, computing their paths independently will count that cell's chocolates twice.
• The Traceback Overhead: To fix this, you would have to run separate DP algorithms, trace back both paths, check for intersecting coordinates, and manually subtract duplicate values. This approach is inefficient, error-prone, and overly complex.
• The Solution: Write a single unified recursion that advances Alice and Bob together row by row.

4. Designing the Unified State Representation

When combining two recursions into one, we must expand our parameter set to track both entities simultaneously at any given moment.

Tracking Rows and Columns

• Row Synchronization: Because both Alice and Bob move down to the next row at every single step, they are always at the same row index i. Thus, we only need a single variable i to represent their current row.
• Column Tracking: Alice and Bob can be in different columns. Therefore, we need two separate column variables:
  • j1: Alice's current column
  • j2: Bob's current column

This gives us our 3-parameter recursive state:

Where:

• i: Current row (ranges from 0 to R - 1)
• j_1: Alice's current column (ranges from 0 to C - 1)
• j_2: Bob's current column (ranges from 0 to C - 1)

5. Step-by-Step Base Cases

When building a recursive solution, always define your base cases first:

1. Out-of-Bounds Base Case

If either Alice or Bob steps outside the valid column boundaries (< 0 or >= C), that path is invalid and must be discarded.

• Why return a very negative number instead of INT_MIN?

  Note: If you return INT_MIN (e.g., -2^31), adding positive integer values to it will cause an integer underflow/overflow, wrapping around to large positive numbers and corrupting your calculation. Instead, return a sufficiently large negative number safely above overflow limits, such as -1e8.

2. Destination Base Case

When i reaches the last row (n - 1), both friends have completed their journey. We must check whether they landed on the same cell:

• If j1 == j2 (same cell): Add the chocolates from that cell once.
• If j1 != j2 (different cells): Add Alice's cell chocolates plus Bob's cell chocolates.

6. Exploring All 9 Simultaneous Paths

At every step i, Alice has 3 possible moves (j1 - 1, j1, j1 + 1) and Bob independently has 3 possible moves (j2 - 1, j2, j2 + 1).

Alice's 3 choices (Left, Down, Right)
   combined with
Bob's 3 choices   (Left, Down, Right)
   = 9 Total Simultaneous Path Combinations per step!

To explore all 9 combinations cleanly without writing nested if-else blocks, we use two inner loops representing column deltas ($\Delta j_1$ and $\Delta j_2$) ranging from -1 to +1:

int maxChocolates = -1e8;

// Loop through all 3 column deltas for Alice
for (int dj1 = -1; dj1 <= 1; dj1++) {
    // Loop through all 3 column deltas for Bob
    for (int dj2 = -1; dj2 <= 1; dj2++) {
        int value = 0;
        
        // Handle overlap condition
        if (j1 == j2) {
            value = grid[i][j1];
        } else {
            value = grid[i][j1] + grid[i][j2];
        }
        
        // Recurse for the next row
        value += f(i + 1, j1 + dj1, j2 + dj2, r, c, grid);
        
        maxChocolates = max(maxChocolates, value);
    }
}
return maxChocolates;

7. Complete Recursive & Memoized 3D DP Solution

Recursive Code (Exponential Time Complexity)

class Solution {
private:
    int solve(int i, int j1, int j2, int r, int c, vector<vector<int>>& grid) {
        // 1. Out-of-bounds base case
        if (j1 < 0 || j1 >= c || j2 < 0 || j2 >= c) {
            return -1e8;
        }
        
        // 2. Destination base case (Last row reached)
        if (i == r - 1) {
            if (j1 == j2) return grid[i][j1];
            else return grid[i][j1] + grid[i][j2];
        }
        
        int maxi = -1e8;
        
        // Explore all 9 combinations of movements for Alice and Bob
        for (int dj1 = -1; dj1 <= 1; dj1++) {
            for (int dj2 = -1; dj2 <= 1; dj2++) {
                int value = 0;
                if (j1 == j2) value = grid[i][j1];
                else value = grid[i][j1] + grid[i][j2];
                
                value += solve(i + 1, j1 + dj1, j2 + dj2, r, c, grid);
                maxi = max(maxi, value);
            }
        }
        return maxi;
    }

public:
    int cherryPickup(vector<vector<int>>& grid) {
        int r = grid.size();
        int c = grid[0].size();
        return solve(0, 0, c - 1, r, c, grid);
    }
};

Adding Memoization (Top-Down DP)

Because subproblems overlap heavily, we can memoize results in a 3D DP table of size R x C x C:

class Solution {
private:
    int solve(int i, int j1, int j2, int r, int c, vector<vector<int>>& grid, vector<vector<vector<int>>>& dp) {
        if (j1 < 0 || j1 >= c || j2 < 0 || j2 >= c) return -1e8;
        
        if (i == r - 1) {
            if (j1 == j2) return grid[i][j1];
            else return grid[i][j1] + grid[i][j2];
        }
        
        if (dp[i][j1][j2] != -1) return dp[i][j1][j2];
        
        int maxi = -1e8;
        for (int dj1 = -1; dj1 <= 1; dj1++) {
            for (int dj2 = -1; dj2 <= 1; dj2++) {
                int value = (j1 == j2) ? grid[i][j1] : grid[i][j1] + grid[i][j2];
                value += solve(i + 1, j1 + dj1, j2 + dj2, r, c, grid, dp);
                maxi = max(maxi, value);
            }
        }
        return dp[i][j1][j2] = maxi;
    }

public:
    int cherryPickup(vector<vector<int>>& grid) {
        int r = grid.size();
        int c = grid[0].size();
        // Declare a 3D DP table initialized to -1
        vector<vector<vector<int>>> dp(r, vector<vector<int>>(c, vector<int>(c, -1)));
        return solve(0, 0, c - 1, r, c, grid, dp);
    }
};

8. Transitioning to Tabulation (Bottom-Up DP)

To convert our memoized solution into a bottom-up iterative approach:

1. Initialize a 3D DP table dp[R][C][C] with zeros.
2. Base Case Population: Fill the last row (i = r - 1) for all possible column combinations of j1 and j2.
3. Nested Loops: Iterate i backwards from R - 2 down to 0. Loop j1 and j2 from 0 to C - 1.
4. Copy the transition logic, referencing dp[i + 1][j1 + dj1][j2 + dj2].

class Solution {
public:
    int cherryPickup(vector<vector<int>>& grid) {
        int r = grid.size();
        int c = grid[0].size();
        
        vector<vector<vector<int>>> dp(r, vector<vector<int>>(c, vector<int>(c, 0)));
        
        // 1. Base Case: Filling the last row
        for (int j1 = 0; j1 < c; j1++) {
            for (int j2 = 0; j2 < c; j2++) {
                if (j1 == j2) dp[r - 1][j1][j2] = grid[r - 1][j1];
                else dp[r - 1][j1][j2] = grid[r - 1][j1] + grid[r - 1][j2];
            }
        }
        
        // 2. Bottom-up filling from row r - 2 down to 0
        for (int i = r - 2; i >= 0; i--) {
            for (int j1 = 0; j1 < c; j1++) {
                for (int j2 = 0; j2 < c; j2++) {
                    
                    int maxi = -1e8;
                    for (int dj1 = -1; dj1 <= 1; dj1++) {
                        for (int dj2 = -1; dj2 <= 1; dj2++) {
                            int value = 0;
                            if (j1 == j2) value = grid[i][j1];
                            else value = grid[i][j1] + grid[i][j2];
                            
                            // Check bounds for next column positions
                            int nextJ1 = j1 + dj1;
                            int nextJ2 = j2 + dj2;
                            if (nextJ1 >= 0 && nextJ1 < c && nextJ2 >= 0 && nextJ2 < c) {
                                value += dp[i + 1][nextJ1][nextJ2];
                            } else {
                                value += -1e8;
                            }
                            maxi = max(maxi, value);
                        }
                    }
                    dp[i][j1][j2] = maxi;
                }
            }
        }
        
        // Starting positions: Alice at (0, 0), Bob at (0, c - 1)
        return dp[0][0][c - 1];
    }
};

9. Space Optimization

In our tabulation solution, computing row i only requires values from the immediately succeeding row i + 1 (the front row).

• Dimensional Reduction: We can reduce the 3D DP table dp[R][C][C] down to a 2D table of size C x C (front and current), saving space across the row dimension.

class Solution {
public:
    int cherryPickup(vector<vector<int>>& grid) {
        int r = grid.size();
        int c = grid[0].size();
        
        vector<vector<int>> front(c, vector<int>(c, 0));
        vector<vector<int>> cur(c, vector<int>(c, 0));
        
        // Base case for the last row
        for (int j1 = 0; j1 < c; j1++) {
            for (int j2 = 0; j2 < c; j2++) {
                if (j1 == j2) front[j1][j2] = grid[r - 1][j1];
                else front[j1][j2] = grid[r - 1][j1] + grid[r - 1][j2];
            }
        }
        
        // Iterating upwards
        for (int i = r - 2; i >= 0; i--) {
            for (int j1 = 0; j1 < c; j1++) {
                for (int j2 = 0; j2 < c; j2++) {
                    int maxi = -1e8;
                    for (int dj1 = -1; dj1 <= 1; dj1++) {
                        for (int dj2 = -1; dj2 <= 1; dj2++) {
                            int value = (j1 == j2) ? grid[i][j1] : grid[i][j1] + grid[i][j2];
                            int nextJ1 = j1 + dj1;
                            int nextJ2 = j2 + dj2;
                            if (nextJ1 >= 0 && nextJ1 < c && nextJ2 >= 0 && nextJ2 < c) {
                                value += front[nextJ1][nextJ2];
                            } else {
                                value += -1e8;
                            }
                            maxi = max(maxi, value);
                        }
                    }
                    cur[j1][j2] = maxi;
                }
            }
            front = cur;
        }
        
        return front[0][c - 1];
    }
};

10. Complexity Analysis Summary

(Where $N$ is the number of rows and $M$ is the number of columns).

11. Summary and Key Takeaways

• Unified Recursion for Multiple Entities: When multiple actors interact on a grid and can overlap, write a single recursive function tracking all their positions simultaneously rather than computing separate paths.
• Synchronized Row Tracking: Because Alice and Bob descend to the next row together at every step, a single row index i is sufficient for both.
• Managing 9 Path Combinations: At each state, nesting two loops from -1 to +1 efficiently generates all 9 possible movement pairs (3 options for Alice × 3 options for Bob).
• Safe Negative Returns: Avoid using INT_MIN for out-of-bound base cases; use a large negative sentinel value like -1e8 to prevent arithmetic overflow when adding positive cell values.
• Handling Overlaps: Explicitly check whether $j_1 == j_2$; if true, collect chocolates from that shared cell only once.
• Dimensional Reduction: Just like 2D DP can be optimized to 1D, 3D DP can be space-optimized by storing only the previous row (front) and current row (cur).