Hints — p78 Cherry Pickup

Hint 1. Greedy “best forward path, then best backward path” looks reasonable but fails. Why? The forward greedy may starve the backward path of a better lane. Need DP.

Hint 2. Key reframing: a round trip (right/down then left/up) is equivalent to TWO simultaneous walks from (0,0) to (n-1,n-1), both moving right/down. Time-reverse the backward walk to see this.

Hint 3. State: (r1, c1, r2, c2) is O(n⁴). Observe both walks take the same number of steps: r1 + c1 = r2 + c2 = t. So c2 = r1 + c1 - r2. State becomes 3D: O(n³).

Hint 4. Gain at each state: if (r1,c1) == (r2,c2), count cherry ONCE. Otherwise sum both cells. Thorns (-1) make the state invalid (-inf).

Hint 5. Recurrence: for each of 4 predecessor combos (each agent moved down or right), take the max. Final answer: max(0, dp[n-1][n-1][n-1]) (clamp -inf to 0 if no valid path).

If stuck: see solution.py.