Grid Paths and Minimum Path Sum

28 min · Intermediate

Some problems ask for a count or a best value over a grid. Many routes share the same cells, so a table that stores one answer per cell does the work once instead of again and again.

Count the routes with a table

Dynamic programming is a method that stores the answer to each smaller version of a problem in a table, so every answer is computed once and reused. It needs a state and a rule that builds a state from smaller ones.

A robot walks on a grid and may only step right or down. How many routes lead from the top-left cell to the bottom-right cell? Any cell is entered from above or from the left, so its count is the sum of those two counts.

Python

1def count_routes(rows, cols):2    ways = [[1] * cols for _ in range(rows)]3    for r in range(1, rows):4        for c in range(1, cols):5            ways[r][c] = ways[r - 1][c] + ways[r][c - 1]6    return ways[-1][-1]7
8
9print(count_routes(3, 3))

Example 1 · Brute force: try every route

Python

1def routes(down, right):2    if down == 0 or right == 0:3        return 14    return routes(down - 1, right) + routes(down, right - 1)5
6
7print(routes(2, 2))

Output

What this code does

routes(2, 2) means two steps down and two steps right. It splits into two smaller calls until one direction is used up.
The same cell is solved again and again, so the time is about 2 to the power (down + right).

Example 2 · Remember answers with a cache

Python

1from functools import cache2
3
4@cache5def routes(down, right):6    if down == 0 or right == 0:7        return 18    return routes(down - 1, right) + routes(down, right - 1)9
10
11print(routes(16, 16))

Output

601080390

What this code does

@cache stores the result of each call, so a cell is solved once.
Only about 17 x 17 calls run. It is the same idea as the table, but top down.

Example 3 · The table version prints its rows

Python

1rows, cols = 3, 42ways = [[1] * cols for _ in range(rows)]3for r in range(1, rows):4    for c in range(1, cols):5        ways[r][c] = ways[r - 1][c] + ways[r][c - 1]6for row in ways:7    print(row)

Output

[1, 1, 1, 1]
[1, 2, 3, 4]
[1, 3, 6, 10]

What this code does

Each inner cell is the sum of the cell above and the cell to its left.
The bottom-right value, 10, is the number of routes on a 3 by 4 grid.

The first row and first column have exactly one route each. Every other cell is filled from two finished neighbours. The cost is O(rows x cols) time and space.

Build the grid the safe way

A grid in Python is a list of rows. Writing [[0] * cols] * rows looks right, but it repeats one row object many times. Change one cell and every row changes. A comprehension makes a fresh row each time.

Python

1bad = [[0] * 3] * 22good = [[0] * 3 for _ in range(2)]3bad[0][1] = 54good[0][1] = 55print(bad)6print(good)

Two ways to build a grid of two rows. With [[0] * 3] * 2, grid[0] and grid[1] both point to one list, so setting grid[0][1] to 5 shows 5 in both rows. With a comprehension, each row points to its own list and only the first row changes.

Example 4 · Copying a grid needs a copy of every row

Python

grid = [[1, 2], [3, 4]]shallow = grid[:]deep = [row[:] for row in grid]grid[0][0] = 99print(shallow[0][0], deep[0][0])

Output

99 1

What this code does

grid[:] copies only the outer list. Both lists still share the same row objects.
[row[:] for row in grid] copies every row, so later changes do not leak.

[0] * 3 is safe because integers cannot change. The trap is repeating a list that holds a list: the outer * copies the reference, not the row.

Minimum path sum

Each cell has a cost. Find the cheapest route from top-left to bottom-right, moving right or down. The best cost to reach a cell is its own cost plus the smaller of the best costs from above and from the left.

Python

1def min_path_sum(cost):2    rows, cols = len(cost), len(cost[0])3    best = [row[:] for row in cost]4    for r in range(rows):5        for c in range(cols):6            if r or c:7                up = best[r - 1][c] if r else float("inf")8                left = best[r][c - 1] if c else float("inf")9                best[r][c] += min(up, left)10    return best[-1][-1]

Example 5 · Minimum path sum and the path itself

Python

1cost = [[1, 3, 1], [1, 5, 1], [4, 2, 1]]2rows, cols = 3, 33best = [row[:] for row in cost]4for r in range(rows):5    for c in range(cols):6        if r or c:7            up = best[r - 1][c] if r else float("inf")8            left = best[r][c - 1] if c else float("inf")9            best[r][c] += min(up, left)10print(best)11r, c = rows - 1, cols - 112path = [(r, c)]13while r or c:14    if r == 0:15        c -= 116    elif c == 0:17        r -= 118    elif best[r - 1][c] < best[r][c - 1]:19        r -= 120    else:21        c -= 122    path.append((r, c))23print(path[::-1])

Output

[[1, 4, 5], [2, 7, 6], [6, 8, 7]]
[(0, 0), (0, 1), (0, 2), (1, 2), (2, 2)]

What this code does

The table holds the cheapest cost to reach every cell. The corner shows 7.
To find the route, start at the corner and step back to the smaller of the two neighbours. Reverse the list to read it forwards.

row[:] copies each row, so the input grid stays unchanged. Missing neighbours on the edges count as infinity, so min ignores them.

Blocked cells and keeping one row

Row r needs only row r - 1 and itself. One list of length cols can hold the whole table and be updated in place. A blocked cell gets zero routes.

Python

1def routes_with_blocks(grid):2    cols = len(grid[0])3    ways = [0] * cols4    ways[0] = 15    for row in grid:6        for c in range(cols):7            if row[c] == 1:8                ways[c] = 09            elif c > 0:10                ways[c] += ways[c - 1]11    return ways[-1]

Example 6 · Routes with blocked cells in one row

Python

1def routes_with_blocks(grid):2    cols = len(grid[0])3    ways = [0] * cols4    ways[0] = 15    for row in grid:6        for c in range(cols):7            if row[c] == 1:8                ways[c] = 09            elif c > 0:10                ways[c] += ways[c - 1]11    return ways[-1]12
13
14grid = [[0, 0, 0], [0, 1, 0], [0, 0, 0]]15print(routes_with_blocks(grid))

Output

What this code does

The centre cell is blocked, so only the route along the top and right edges and the route along the left and bottom edges remain.
A blocked cell sets its count to zero, which also removes everything that depends on it.

Example 7 · Python integers never overflow

Python

1def count_routes(rows, cols):2    ways = [[1] * cols for _ in range(rows)]3    for r in range(1, rows):4        for c in range(1, cols):5            ways[r][c] = ways[r - 1][c] + ways[r][c - 1]6    return ways[-1][-1]7
8
9print(count_routes(50, 50))

Output

25477612258980856902730428600

What this code does

The answer has 29 digits. A fixed-size integer in many languages would overflow, but a Python int grows as needed.
You only take a remainder when the problem statement asks for one.

Before an update, ways[c] still holds the cell above and ways[c - 1] already holds the cell to the left. Space falls from O(rows x cols) to O(cols).

Next step

Check your understanding

11 quick questions

Count the routes with a table

1def count_routes(rows, cols):2 ways = [[1] * cols for _ in range(rows)]3 for r in range(1, rows):4 for c in range(1, cols):5 ways[r][c] = ways[r - 1][c] + ways[r][c - 1]6 return ways[-1][-1]7 8 9print(count_routes(3, 3))

1from functools import cache2 3 4@cache5def routes(down, right):6 if down == 0 or right == 0:7 return 18 return routes(down - 1, right) + routes(down, right - 1)9 10 11print(routes(16, 16))

1def min_path_sum(cost):2 rows, cols = len(cost), len(cost[0])3 best = [row[:] for row in cost]4 for r in range(rows):5 for c in range(cols):6 if r or c:7 up = best[r - 1][c] if r else float("inf")8 left = best[r][c - 1] if c else float("inf")9 best[r][c] += min(up, left)10 return best[-1][-1]

1cost = [[1, 3, 1], [1, 5, 1], [4, 2, 1]]2rows, cols = 3, 33best = [row[:] for row in cost]4for r in range(rows):5 for c in range(cols):6 if r or c:7 up = best[r - 1][c] if r else float("inf")8 left = best[r][c - 1] if c else float("inf")9 best[r][c] += min(up, left)10print(best)11r, c = rows - 1, cols - 112path = [(r, c)]13while r or c:14 if r == 0:15 c -= 116 elif c == 0:17 r -= 118 elif best[r - 1][c] < best[r][c - 1]:19 r -= 120 else:21 c -= 122 path.append((r, c))23print(path[::-1])

1def routes_with_blocks(grid):2 cols = len(grid[0])3 ways = [0] * cols4 ways[0] = 15 for row in grid:6 for c in range(cols):7 if row[c] == 1:8 ways[c] = 09 elif c > 0:10 ways[c] += ways[c - 1]11 return ways[-1]