Cheapest route from top-left to bottom-right

Dynamic programming Junior Python 3.13+ Reviewed 1 Nov 2026 By Best Latest Apps

Predict the output

What does this print?

Python 3.13

import math
grid = [[1, 3, 1], [1, 5, 1], [4, 2, 1]]
row = [math.inf] * 3
row[0] = 0
for cells in grid:
    for c, cost in enumerate(cells):
        left = row[c - 1] if c else math.inf
        row[c] = cost + min(row[c], left)
print(row)

Options[6, 8, 7][7, 8, 7][6, 9, 8]

Choose an answer, then open Show answer below to check it.

Show answer

Answer: A [6, 8, 7]

Right: the bottom-right cell is 7 via 1, 3, 1, 1, 1, and the first column sums to 6.

The rolling row holds the cheapest cost into each column of the current row, so its last entry is the answer.

Why not the others?

B [7, 8, 7]. The bottom-left cell has only one way in: 1 + 1 + 4 = 6.
C [6, 9, 8]. Each cell takes the cheaper of above and left.

30-second answer

The cheapest way into a cell comes from the cheaper of the cell above and the cell to its left, so cost[r][c] = grid[r][c] + min(above, left). The first row and column have only one way in. O(R × C) time, one row of memory: O(C).

Practise saying it · 45 s. No recording, just a timer

Explain the cheapest grid route.

Say your answer out loud, then check which of these points you covered:

cost = cell + min(above, left)
Edges have one way in
O(R × C)

Deep dive

Same table as counting routes, with min and + instead of +.

Non-negative costs matter only if moves could go back; with right and down only, any costs work.

With moves in all four directions this becomes a shortest-path question (Dijkstra).

Python solution Ran on Python 3.13.5 · mypy --strict

Python 3.13

import math


def cheapest_route(grid: list[list[int]]) -> int:
    row = [math.inf] * len(grid[0])  # cheapest cost into each column
    row[0] = 0
    for cells in grid:
        for c, cost in enumerate(cells):
            from_left = row[c - 1] if c else math.inf
            row[c] = cost + min(row[c], from_left)
    return int(row[-1])

Common mistakes

Treating the first row like the inner cells and reading outside the grid.
Forgetting to include the starting cell's cost.

Senior take & follow-ups

Point out that only right and down moves make a simple fill order possible.

Follow-up questions

Think of your answer first, then open the hint.

How do you print the route?
Show hint
Keep the full table and walk back from the end, stepping to the cheaper of up or left.
What if you can move in four directions?
Show hint
Use Dijkstra on the grid with cell costs as edge weights.

What each operation costs: Two Dimensional Arrays

From the author

DSA Master - Data & Algorithms

Free on iPhone and iPad: watch 50+ data structures and algorithms step through animations, run the code in the playground, and try the daily challenge.

Get it on the App Store

Suggest a fix if something here is wrong or out of date.