Why it works
- Every path into (r, c) arrives from (r - 1, c) or from (r, c - 1). The cheapest one is the cheapest way into the better of those two plus the cost of (r, c), so min of two finished cells is enough.
- A cell on the top row or the left column has one way in; the missing side counts as ∞, so min always takes the real one.
- Picking the cheaper next cell at each step is not enough: here the 1 to the right of the start leads to a total of 14, while the table finds 12 by going down first.
Complexity
Time O(m × n): each cell is one min and one addition. Memory O(m × n) for the table; a cell reads only its row and the row above, so one row of n cells is enough, or the grid itself can be overwritten.
nextNow solve it yourself, no hints.
Solve on LeetCode ↗