AlgoScope

Minimum Path Sum

cost(r, c) = grid(r, c) + min(cost(r-1, c), cost(r, c-1)).

Dynamic programming, algorithm, beginner
Cell 1, 1 becomes 7.012012145271421
Cell 1, 1 becomes 7.012012145271421

DP on a Grid: Cheapest path

Decision, step 6 of 11

(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.

How dp on a grid works

Cost

Best
O(r * c)
Average
O(r * c)
Worst
O(r * c)
Space
O(c)

Taught by the same lesson

DP on a Grid covers these too, in the same run.