Minimum-cost path through a grid

Question

You're given a grid of tolls. Starting at the top-left cell and moving only right or down, reach the bottom-right cell, paying the value of every cell you pass through.

grid = [[1, 3, 1],
        [1, 5, 1],
        [4, 2, 1]]
-> 7           # path 1 -> 3 -> 1 -> 1 -> 1

Return the minimum total toll. Aim for $O(nm)$ .

Accepted Answer

Let dp[r][c] be the cheapest total for any valid path ending at (r, c). The last move comes from the left or from above, so dp[r][c] = 	ext{grid}[r][c] + \min(dp[r-1][c],\; dp[r][c-1]), with the first row and first column having only one feasible predecessor. Fill row by row; the answer sits in the bottom-right cell. On the example the dp table's bottom row is 6, 8, 7, so the answer is 7, the path 1, 3, 1, 1, 1 down the top and right edges. Time O(nm), space O(nm), reducible to O(m) by keeping just the current row. Takeaway. Minimum-path-sum is maximum-path-sum with \min swapped for \max: sa…

Minimum-cost path through a grid

Your answer

More Coding questions