Minimum Path Sum
cost(r, c) = grid(r, c) + min(cost(r-1, c), cost(r, c-1)).
Decision · step 6 of 11DP on a Grid: Cheapest path
(1, 1) costs 5. Coming from above totals 4, from the left 2. Take the cheaper: 5 + min(4, 2) = 7. The cheapest way here must end with the cheapest way to one of those two cells.
What you will see
Same arrows as grid paths but the smaller source wins; the chosen path is traced back at the end.
Cost
| Best | O(r * c) |
|---|---|
| Average | O(r * c) |
| Worst | O(r * c) |
| Space | O(c) |
How you work with it here
play it through, step one change at a time, scrub to any step, run it on your own input, predict what happens next.
Screen readers: Table cells announce their state and value; each step announces which cells were read and the value written.
Reduced motion: Dependency arrows appear statically and the cell value crossfades.
Before this
Taught by the same lesson
DP on a Grid covers these too, in the same run.