Minimum Path Sum and Unique Paths: Dynamic Programming on Grids

Grid problems are where dynamic programming stops being abstract. Minimum path sum and unique paths are the two classic versions, and they are the same algorithm with one operator changed. Once you see why a cell only ever needs two neighbours, a whole family of interview questions, from obstacles to falling paths to dungeon games, turns into filling a table in the right order.

The problem it solves

You start in the top-left cell of a grid and must reach the bottom-right, moving only right or down.

• Minimum path sum: each cell has a cost. Find the smallest total along any route. For [[1, 3, 1], [1, 5, 1], [4, 2, 1]] the answer is 7.
• Unique paths: count the routes. A 3 by 3 grid of cells has 6; a 3 by 7 grid has 28. A variant marks some cells as blocked.

The brute force tries every route. A route on an m by n grid is a sequence of m - 1 downs and n - 1 rights, so there are C(m + n - 2, m - 1) of them. That number explodes: a 16 by 16 grid already has over 155 million routes. Most of them share long stretches, and the brute force recomputes those stretches over and over.

The intuition

Look at one cell and ask: how could a route arrive here? With moves limited to right and down, only from the cell above or the cell to the left. Nothing else can touch it.

So if you already know the best total for those two cells, the best total here is:

• Cheapest route: the smaller of the two, plus this cell's own cost.
• Number of routes: the two counts added together, because every route in arrives through exactly one of them.

That is the whole recurrence. The table order follows from it: fill row by row, left to right, and both neighbours are always ready before you need them. The first row and first column have only one way in, so their values are running sums along the edge (for costs) or all ones (for counts).

The table also encodes the route: from the goal, step back to whichever neighbour produced the smaller value until you reach the start.

Watch it run

The animation frames the lesson's grid as a climb map: each square costs metres of climb, and walking only east or south, the question is the gentlest crossing. The start square has no way in, so its running total is just its own climb, 1. On the edge there is only one way in, so the top row reads 1 + 3 = 4 and then 4 + 1 = 5, and the left column 1 + 1 = 2. The centre has two ways in: from above (4) or from the left (2). Take the gentler and add 5, giving 7. The right-hand square of the middle row picks 5 from above over 7 from the left and becomes 6. The bottom row goes 2 + 4 = 6, then 6 from the left beats 7 from above for 8, and the goal takes 6 from above over 8 for 7. Then the route lights up: 1 + 3 + 1 + 1 + 1 = 7, the cheapest crossing, found square by square rather than by trying all six routes. Finally, swap min for + and the same two neighbours count routes instead: 6 ways across a 3 by 3 grid.

The code

The lesson's table, returned whole so the route can be read back:

def min_path_sum(grid):
    rows, cols = len(grid), len(grid[0])
    cost = [row[:] for row in grid]
    for i in range(rows):
        for j in range(cols):
            if i or j:                                    # the start has no way in
                above = cost[i - 1][j] if i else float("inf")
                left = cost[i][j - 1] if j else float("inf")
                cost[i][j] += min(above, left)            # cheapest way in
    return cost

grid = [[1, 3, 1],
        [1, 5, 1],
        [4, 2, 1]]
cost = min_path_sum(grid)
print(cost)                  # [[1, 4, 5], [2, 7, 6], [6, 8, 7]]
print(cost[-1][-1])          # 7

Reading the route back from the goal, preferring "above" on a tie as the animation does:

def read_path(grid, cost):
    i, j = len(grid) - 1, len(grid[0]) - 1
    path = [(i, j)]
    while i or j:
        if j == 0 or (i and cost[i - 1][j] <= cost[i][j - 1]):
            i -= 1                                        # came from above
        else:
            j -= 1                                        # came from the left
        path.append((i, j))
    return path[::-1]

route = read_path(grid, cost)
print(route)                             # [(0, 0), (0, 1), (0, 2), (1, 2), (2, 2)]
print([grid[i][j] for i, j in route])    # [1, 3, 1, 1, 1]

Counting routes with the + version, in a single row that is overwritten as it goes. Before the update, ways[j] still holds the value from the row above, and ways[j - 1] already holds the cell to the left. A blocked cell contributes zero:

def unique_paths(rows, cols, blocked=()):
    ways = [0] * cols                                     # one row, reused
    ways[0] = 1
    for i in range(rows):
        for j in range(cols):
            if (i, j) in blocked:
                ways[j] = 0
            elif j:
                ways[j] += ways[j - 1]                    # above (old value) + left
    return ways[-1]

print(unique_paths(3, 3))                # 6
print(unique_paths(3, 7))                # 28
print(unique_paths(3, 3, {(1, 1)}))      # 2

Against the brute force that walks every route, on 1,500 random grids with random blocked cells:

from itertools import combinations
import random

def all_paths(rows, cols):
    downs = rows - 1
    steps = rows + cols - 2
    for down_at in combinations(range(steps), downs):
        i = j = 0
        cells = [(0, 0)]
        for s in range(steps):
            if s in down_at:
                i += 1
            else:
                j += 1
            cells.append((i, j))
        yield cells

random.seed(19)
ok = True
for _ in range(1500):
    r, c = random.randint(1, 5), random.randint(1, 5)
    g = [[random.randint(0, 9) for _ in range(c)] for _ in range(r)]
    blocked = {(random.randrange(r), random.randrange(c)) for _ in range(random.randint(0, 3))}
    blocked -= {(0, 0)}
    paths = list(all_paths(r, c))
    cost = min_path_sum(g)
    ok &= cost[-1][-1] == min(sum(g[i][j] for i, j in p) for p in paths)
    ok &= sum(g[i][j] for i, j in read_path(g, cost)) == cost[-1][-1]
    ok &= unique_paths(r, c, blocked) == sum(not blocked & set(p) for p in paths)
print(ok)                                # True

The complexity

• Time: O(m·n). Each cell is filled once from two neighbours.
• Space: O(m·n) for the full table, which you need if you want to read the route back. For the total or the count alone, one row of n values is enough, O(n), or O(min(m, n)) if you iterate along the shorter side.
• Unique paths has a closed form: C(m + n - 2, m - 1), because a route is just a choice of which steps go down. It stops helping once obstacles appear, while the table keeps working.

Where it goes wrong

• Treating the edges like the interior. The first row and column have one way in. Initialising them to zero or leaving them out gives wrong totals or index errors.
• Using zero as "no way in" for costs. A missing neighbour must be infinity in a min, or the walk appears to arrive for free from outside the grid.
• Filling in the wrong order. Any order where a cell is computed before the one above it or to its left reads unfinished values.
• Assuming the recurrence survives more moves. If moves go up or left as well, the grid has cycles and this table no longer applies; that is a shortest-path problem for Dijkstra's algorithm.
• Overflowing the count. Route counts grow fast; fixed-width integers overflow where Python's do not.

When it shows up in interviews

Unique paths and minimum path sum are among the most common introductions to 2D dynamic programming, and interviewers often chain them: count the routes, then add obstacles, then ask for the cheapest route, then ask you to print it, then ask for O(n) space. The same shape appears in dungeon-style problems filled from the bottom-right, in the maximal square problem, and in string DP such as edit distance, where the "grid" is two strings against each other.

How to say it in an interview

"With only right and down moves, a cell can only be entered from above or from the left, so its best value depends on just those two. For the cheapest route I take the smaller one and add the cell's cost; to count routes I add them. I fill row by row so both neighbours are ready, with the first row and column as running sums because they have a single way in. That is O(m·n) time. If I only need the number, I keep one row and update it in place, because the old value is the cell above and the new left neighbour is already updated. If I need the route, I keep the table and walk back from the goal to whichever neighbour gave the smaller value."