Unique Paths

Medium·🗺️ 2-D Dynamic Programming·Open on LeetCode ↗

Count the distinct routes from the top-left corner of a grid to the bottom-right, moving only right or down.

a 4 × 5 gridstep 1/15

How many ways to reach each cell? Arrivals come only from above or from the left.

1def unique_paths(m, n):
2    dp = [[1] * n for _ in range(m)]
3    for r in range(1, m):
4        for c in range(1, n):
5            dp[r][c] = dp[r - 1][c] + dp[r][c - 1]
6    return dp[m - 1][n - 1]

Read the 15 steps as text

1How many ways to reach each cell? Arrivals come only from above or from the left.
2Along the top row and the first column there is exactly one route to every cell.
3(1, 1): 1 from above + 1 from the left = 2.
4(1, 2): 1 from above + 2 from the left = 3.
5(1, 3): 1 from above + 3 from the left = 4.
6(1, 4): 1 from above + 4 from the left = 5.
7(2, 1): 2 from above + 1 from the left = 3.
8(2, 2): 3 from above + 3 from the left = 6.
9(2, 3): 4 from above + 6 from the left = 10.
10(2, 4): 5 from above + 10 from the left = 15.
11(3, 1): 3 from above + 1 from the left = 4.
12(3, 2): 6 from above + 4 from the left = 10.
13(3, 3): 10 from above + 10 from the left = 20.
14(3, 4): 15 from above + 20 from the left = 35.
15The bottom-right corner holds every route: 35.

The idea

Ask a smaller question: how many ways are there to reach one particular cell? You can only arrive from above or from the left, and those two sets of routes are disjoint — a route arrives from exactly one direction. So the count for a cell is the count above plus the count to the left.

That single sentence is the whole recurrence. The edges are the base case: along the top row you can only ever have come from the left, so there is exactly one route to each; same down the first column.

Fill the grid top-to-bottom, left-to-right and every cell's two inputs are already computed by the time you need them. No recursion, no memo table to invalidate — just a grid being filled in reading order.

You may notice the answer is a binomial coefficient — the number of ways to arrange the required downs among the total moves. That's a legitimate O(m + n) answer and worth saying out loud, but the grid is the version that survives obstacles being added in the follow-up.

The approach

1Make a grid of counts the same size as the board.
2Fill the first row and first column with 1 — there is exactly one way to reach any of them.
3For every other cell, add the value above to the value on the left.
4The bottom-right cell holds the answer.

Complexity

Time

O(m × n)

Space

O(m × n)

Each cell is computed once from two neighbours. Only the previous row is ever read, so the space collapses to O(n) with a single rolling row.

Code

def unique_paths(m, n):
    dp = [[1] * n for _ in range(m)]
    for r in range(1, m):
        for c in range(1, n):
            dp[r][c] = dp[r - 1][c] + dp[r][c - 1]
    return dp[m - 1][n - 1]

What goes wrong

•Filling in the wrong order. A cell needs its top and left neighbours to be final already; iterate row-major and they always are.
•Forgetting to seed the first row and column, which leaves them as zeros and drives the whole grid to zero.
•Reaching for plain recursion without memoization. It re-derives the same cells exponentially many times and times out on a grid that the loop version finishes instantly.