Unique Paths

Unique Paths is the friendliest introduction to grid dynamic programming. It looks like a combinatorics puzzle, but the cleanest solution just fills in a table where every cell is the sum of two neighbors.

The slow way first

The brute-force idea is recursion: from any cell, the number of paths is "paths if I go right" plus "paths if I go down." Count both and add them.

That works, but it re-explores the same cells over and over — the recursion tree is exponential. The fix is to notice that the answer for each cell only depends on its right-neighbor and down-neighbor, so we can compute each cell once and store it.

The idea: every cell is above + left

Let dp[i][j] be the number of distinct paths from the start to cell (i, j). Two facts give us the whole table:

• The first row and first column are all 1 — there is only one straight-line way to reach them (all rights, or all downs).
• Every other cell is reached only from above or from the left, so dp[i][j] = dp[i-1][j] + dp[i][j-1].

Fill the grid top-to-bottom, left-to-right, and the bottom-right cell holds the final count.

Walk through it

Step through the animation. First the top row and left column are seeded with 1. Then each inner cell lights up its two source cells (above and left) and shows their sum: dp[1][1] = 2, then 3, 3, and finally the corner dp[2][2] = 3 + 3 = 6.

Pseudocode

make an m-by-n grid called "dp", all entries start at 1
for each cell in the first row: it stays 1 (one way: all rights)
for each cell in the first column: it stays 1 (one way: all downs)
for i from 1 to m-1:
    for j from 1 to n-1:
        dp[i][j] = dp[i-1][j] + dp[i][j-1]   # above + left
return dp[m-1][n-1]                           # the bottom-right corner

The Python solution

def unique_paths(m, n):
    dp = [[1] * n for _ in range(m)]
    for j in range(n):
        dp[0][j] = 1
    for i in range(1, m):
        dp[i][0] = 1
        for j in range(1, n):
            above = dp[i - 1][j]
            left = dp[i][j - 1]
            dp[i][j] = above + left
    return dp[m - 1][n - 1]

• dp starts as an m × n grid of 1s, which already takes care of the first row and column.
• The first two loops make the seeding explicit: the top row and left column are each 1.
• The inner double loop fills every other cell as above + left — the heart of the recurrence.
• above is the cell directly up, left is the cell directly to the left.
• We return dp[m-1][n-1], the bottom-right corner, which holds the total path count.

Complexity

We fill every cell exactly once and each fill is one addition, so the work is O(m·n). The grid itself uses O(m·n) space — and you can shrink that to O(n) by keeping only one row at a time, since each cell only needs the row above.

When this pattern shows up

Practice