Cherry Pickup
hardTime: O(n³)Space: O(n³)
Signals to notice
two paths collecting cherriessimultaneous traversalcan't double-count
Brute force first
Two-pass greedy — provably suboptimal.
The key insight
3D DP: both paths move simultaneously. dp[step][c1][c2]. If same cell, count once. O(n³).
What must stay true
Simultaneous movement with same step count: r1+c1 = r2+c2. If same cell, cherries counted once.
Easy way to go wrong
Two-pass greedy is WRONG — must optimize both paths jointly.