Cheapest Path Across a Grid
Problem
A grid holds a non-negative cost in every cell. You start in the top-left cell and must reach the bottom-right cell, moving only right or down. Return the smallest possible sum of the costs of the cells you pass through, including the first and last cells.
Examples
Input: grid = [[1, 3, 1], [1, 5, 1], [4, 2, 1]]
Output: 7
Why: right, right, down, down visits 1, 3, 1, 1, 1 and avoids the 5 in the middleInput: grid = [[2, 1, 4], [3, 1, 1]]
Output: 5
Why: right, down, right visits 2, 1, 1, 1Input: grid = [[7]]
Output: 7
Why: edge case, the start is also the finishHints
0 / 3
Picking the cheaper neighbour at each step is a trap, since a cheap step can lead into an expensive region. The number of paths grows too fast to try them all.
The only ways into a cell are from the cell above it and the cell to its left. So the cheapest cost to reach a cell is its own cost plus the cheaper of those two cheapest costs.
Build a table the size of the grid. The top-left entry is its own cost, the first row can only come from the left, and the first column only from above. Every other entry is its cost plus the minimum of the entry above and the entry to the left. The answer is the bottom-right entry.
Solution
Every path into a cell arrives from above or from the left, so the cheapest way to reach it extends the cheaper of those two cheapest ways. Filling the table row by row guarantees both neighbours are final before a cell needs them. The first row and first column have only one way in, which is why they are handled on their own. Time is O(rows · cols) and space is O(rows · cols), and because each row only reads the row above it, a single row of the table is enough if memory matters.
def cheapest_path(grid):
rows, cols = len(grid), len(grid[0])
cost = [[0] * cols for _ in range(rows)]
for r in range(rows):
for c in range(cols):
if r == 0 and c == 0:
cost[r][c] = grid[r][c]
elif r == 0:
cost[r][c] = cost[r][c - 1] + grid[r][c] # top row: only from the left
elif c == 0:
cost[r][c] = cost[r - 1][c] + grid[r][c] # left column: only from above
else:
cost[r][c] = min(cost[r - 1][c], cost[r][c - 1]) + grid[r][c]
return cost[-1][-1]
print(cheapest_path([[1, 3, 1], [1, 5, 1], [4, 2, 1]])) # -> 7
print(cheapest_path([[2, 1, 4], [3, 1, 1]])) # -> 5
print(cheapest_path([[7]])) # -> 7Stuck on the idea rather than the code? DP on Grids covers it.