Cherry Pickup II - Video Solutions

Problem Overview: You control two robots starting at the top row of a grid. One begins at the leftmost column and the other at the rightmost column. Each step both robots move to the next row and can shift left, stay, or shift right. The goal is to collect the maximum number of cherries while ensuring a cell's cherries are counted once if both robots land on it.

Approach 1: Recursive Approach with Memoization (Time: O(rows * cols²), Space: O(rows * cols²))

Model the problem using a recursive state (row, col1, col2) representing the current row and the column positions of both robots. From this state, explore all 9 possible next moves because each robot can move to col-1, col, or col+1. Add cherries from the current cells and recursively compute the best outcome for the next row. Without caching, the search explodes exponentially. Memoization stores results for each state so repeated subproblems are reused. A 3D memo table or hash map avoids recomputation and keeps the complexity bounded. This approach maps naturally to the problem definition and is often the easiest way to derive the correct transition logic.

Approach 2: Dynamic Programming (Bottom-Up) (Time: O(rows * cols²), Space: O(rows * cols²))

The optimized solution converts the recursive idea into bottom-up dynamic programming. Define dp[row][c1][c2] as the maximum cherries collected when robot1 is at column c1 and robot2 is at column c2 on a given row. Iterate row by row through the matrix. For each pair of columns, compute the best value from the 9 previous column combinations. Add cherries from grid[row][c1] and grid[row][c2], making sure to count only once if c1 == c2. This DP effectively tracks both robots simultaneously while exploring all movement combinations. Since there are rows levels and roughly cols² column pairs per level, the total work stays manageable.

The key insight is that both robots always move downward together. That means the row index is shared, reducing the state to three variables instead of tracking full paths. Treating the robots' positions as a pair avoids double counting and keeps transitions local to the previous row.

Recommended for interviews: The bottom-up dynamic programming approach is what most interviewers expect. It demonstrates that you can convert a recursive state definition into an efficient tabulation strategy. Starting with the memoized recursion shows understanding of the state transition, while implementing the DP version proves you can optimize overlapping subproblems. Problems involving two agents moving through a grid commonly appear in array and DP interview rounds, especially when the solution requires multi-dimensional state design.