Minimum Path Sum
cost(r, c) = grid(r, c) + min(cost(r-1, c), cost(r, c-1)).
DP 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.
Cost
- Best
- O(r * c)
- Average
- O(r * c)
- Worst
- O(r * c)
- Space
- O(c)
Before this
Taught by the same lesson
DP on a Grid covers these too, in the same run.