Cherry Pickup II

Cherry Pickup II

What is this problem about?

In Cherry Pickup II, you have two robots starting at the top-left $(0, 0)$ and top-right $(0, n-1)$ of a grid. Both robots move down to the bottom row. In each step, a robot can move to the cell below, below-left, or below-right. If both robots land in the same cell, only one collects the cherries. The goal is to maximize the total cherries collected by both robots.

Why is this asked in interviews?

Companies like Uber and Google use this to test your ability to handle 3D Dynamic Programming. Unlike the first Cherry Pickup, the robots move strictly downwards, which simplifies the state but still requires you to manage the interaction between two paths. It evaluations your skill in state transitions and handling boundary conditions.

Algorithmic pattern used

This is a 3D Dynamic Programming problem. The state is dp[row][col1][col2], representing the maximum cherries collected when Robot 1 is at (row, col1) and Robot 2 is at (row, col2). Since both robots move down one row in every step, we only need to track the current row. For each state, there are $3 imes 3 = 9$ possible previous states to consider (each robot could have come from 3 positions).

Example explanation

Row 0: Robot 1 at (0,0), Robot 2 at (0, 6) in a $7 imes 7$ grid. Row 1:

• Robot 1 can move to (1,0), (1,1).
• Robot 2 can move to (1,5), (1,6). We calculate the cherries at the current positions and add the max cherries possible from any of the 9 valid pairs of positions in the previous row.

Common mistakes candidates make

A common mistake is not handling the "same cell" condition correctly—Robot 1 and Robot 2 should not both add the cherries if col1 == col2. Another error is not properly checking the grid boundaries for the diagonal moves (below-left and below-right). Using a 3D array for DP is fine, but you can optimize it to use only two 2D arrays (current row and previous row) to save space.

Interview preparation tip

Practice visualizing the state transitions. In 3D DP, it's helpful to think: "To be in this state at Row $I$, where could I have been at Row $I-1$?". This bottom-up thinking is the core of dynamic programming.