Cherry Pickup
hardTime: O(n³)Space: O(n³)
Recognize the pattern
two paths collecting cherriessimultaneous traversalcan't double-count
Brute force idea
Two-pass greedy — provably suboptimal.
Better approach
3D DP: both paths move simultaneously. dp[step][c1][c2]. If same cell, count once. O(n³).
Key invariant
Simultaneous movement with same step count: r1+c1 = r2+c2. If same cell, cherries counted once.
Watch out for
Two-pass greedy is WRONG — must optimize both paths jointly.