Cheapest path through a fee grid

Question

You must move a position from the top-left cell of a grid to the bottom-right, stepping only right or down. Each cell charges a transaction fee (its value). Minimize the total fees paid, counting both endpoints.

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

Return the minimum total cost of a right/down path from corner to corner in O(m*n) time.

Accepted Answer

Let dp[i][j] be the cheapest cost to reach cell (i, j). Since you can only arrive from above or from the left, dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1]). Fill the first row and first column first (they have only one way in), then sweep the interior. For the example the cheapest route 1 - 3 - 1 - 1 - 1 totals 7. Time O(mn), space O(mn), reducible to O(n) with a single rolling row. Edge cases: a 1x1 grid returns its only cell; because moves are restricted to right/down, this stays a simple DP (add diagonal or up/left moves and you would need Dijkstra). Takeaway. Monotone grid movement…

Cheapest path through a fee grid

Your answer

More Coding questions