Cherry Pickup
Hard · Dynamic Programming · about 40 minutes
Asked at Google, Amazon, Microsoft, Meta.
An n × n grid has 1 (a cherry), 0 (empty) and -1 (a thorn, impassable). Go from (0, 0) to (n-1, n-1) moving right/down, then return moving left/up, picking up every cherry on the way (each cell's cherry can be picked once). Return the maximum cherries, or 0 if no valid path exists.