Cherry Pickup

Cherry Pickup

What is this problem about?

You are given an $n imes n$ grid with cherries (1), empty spaces (0), and thorns (-1). You start at (0, 0), move to (n-1, n-1) picking up cherries, and then return to (0, 0) picking up more. Thorns are impassable. Once a cherry is picked, the cell becomes empty. The goal is to maximize the total number of cherries collected.

Why is this asked in interviews?

This is a classic "Hard" Dynamic Programming problem asked by nearly every top-tier company (Google, Amazon, Meta). It tests your ability to transform a two-pass problem into a single-pass problem. You can't just find the best path forward and then the best path back (that's a greedy error); you must simulate two people moving from (0,0) to (n-1, n-1) simultaneously.

Algorithmic pattern used

The pattern is Dynamic Programming on a Matrix with simultaneous paths. We track the state $(t, r1, r2)$, where $t$ is the number of steps taken (time), $r1$ is the row of the first person, and $r2$ is the row of the second person. The columns can be derived as $c1 = t - r1$ and $c2 = t - r2$. At each step, if both people are at the same cell, you only count the cherry once.

Example explanation

Grid: 1 1 1 0 0 0 0 0 1

1. Two paths starting at (0,0).
2. Step 1: P1 goes Right (0,1), P2 goes Down (1,0).
3. Continue until both reach (n-1, n-1).
4. If P1 and P2 both pass through (0,1), the cherry is only added once to the total. By moving them simultaneously, we account for all possible interactions between the forward and backward paths.

Common mistakes candidates make

The most common mistake is the "Greedy" approach: find the max path from A to B, remove those cherries, then find the max path from B to A. This doesn't work because the "best" first path might leave the second path with very few options. Another mistake is using a 4D DP state $(r1, c1, r2, c2)$, which is $O(N^4)$ and might time out, whereas $O(N^3)$ is sufficient.

Interview preparation tip

Whenever a problem involves a "round trip" in a grid, try to reframe it as two people moving from the start to the end at the same time. This is a recurring pattern in path optimization problems.