Unique Paths in Grid, in depth: the recurrence, one-row DP, the binomial closed form and its overflow trap, obstacles and huge grids

The recurrence

Name cells (r, c) from (0, 0) at the top left. The last move into (r, c) came either from above, (r - 1, c), or from the left, (r, c - 1). These two sets of routes are disjoint, because they differ in their final step. Together they cover every route. So by the addition rule:

paths(0, c) = 1                 # first row: only rightward moves
paths(r, 0) = 1                 # first column: only downward moves
paths(r, c) = paths(r - 1, c) + paths(r, c - 1)

This is optimal substructure in its plainest form. The count for a cell depends only on two smaller subproblems, and those subproblems overlap heavily. Plain recursion therefore takes exponential time. The table fills in O(mn) time, as the general dynamic programming guide explains for the whole family.

One row is enough

Row r needs only row r - 1. One array of length n is enough, updated left to right. Before the update dp[c] holds the value from above, and dp[c - 1] already holds the new value from the left.

def unique_paths(m: int, n: int) -> int:
    if m <= 0 or n <= 0:
        return 0
    if n > m:                        # keep the array on the shorter side
        m, n = n, m
    dp = [1] * n
    for _ in range(1, m):
        for c in range(1, n):
            dp[c] += dp[c - 1]
    return dp[-1]

assert unique_paths(3, 7) == 28
assert unique_paths(1, 1) == 1

Time is O(mn) and memory O(min(m, n)). Swapping so that the array runs along the short side matters for 10 by 1,000,000 grids, where it is the difference between ten numbers and a million.

The closed form and its overflow trap

Every route has exactly m - 1 down moves and n - 1 right moves, in some order. A route is a choice of which of the m + n - 2 steps are downs, so the count is C(m + n - 2, m - 1). For 3 by 7 that is C(8, 2) = 28, matching the table. The combinatorics article covers the counting rules behind this. The closed form costs O(min(m, n)) arithmetic operations:

def unique_paths_closed(m: int, n: int) -> int:
    k = min(m, n) - 1
    total = m + n - 2
    r = 1
    for i in range(1, k + 1):
        r = r * (total - k + i) // i   # exact: r is C(total - k + i, i) after each step
    return r

The division is always exact, because after step i the running value is itself a binomial coefficient. Python integers never overflow, but fixed-width ports do, and at different sizes:

The row at side 32 is the subtle one. The DP only ever adds, so its values never exceed the answer. The multiply-then-divide loop builds an intermediate value larger than the answer. A C or Java port of the closed form therefore fails on inputs where the DP would have succeeded. Fixes include dividing by the gcd before multiplying, using 128-bit intermediates, or using the DP.

Obstacles

With blocked cells, the recurrence still holds. Blocked cells contribute zero, and the first row and column are no longer all ones, because a block cuts off everything after it.

def unique_paths_obstacles(grid: list[list[int]]) -> int:
    """grid[r][c] == 1 means blocked."""
    if not grid or not grid[0]:
        return 0
    n = len(grid[0])
    dp = [0] * n
    dp[0] = 1 if grid[0][0] == 0 else 0          # a blocked start means zero paths
    for row in grid:
        for c in range(n):
            if row[c] == 1:
                dp[c] = 0
            elif c > 0:
                dp[c] += dp[c - 1]
    return dp[-1]

g = [[0, 0, 0, 0, 0],
     [0, 1, 0, 0, 0],
     [0, 0, 0, 1, 0],
     [0, 0, 0, 0, 0]]
assert unique_paths_obstacles(g) == 7

Trace it on the 4 by 5 grid in the diagram. Row 0 is all ones. In row 1 the block at column 1 zeroes that cell, so the row reads 1, 0, 1, 2, 3. Row 2 reads 1, 1, 2, 0, 3, and row 3 ends at 7. Without obstacles the answer would be C(7, 3) = 35.

Huge grids with few obstacles

If the grid is 100,000 by 100,000 with a few hundred blocked cells, the table is impossible but the closed form still works between points. Sort the blocked cells by row, then column. Add the target as a final point. For each point, compute f(i), the number of routes that reach it without touching an earlier blocked cell. That is all routes to it, minus routes that first hit some earlier blocked cell j and then continue to i:

def paths_avoiding(points, target, MOD=10**9 + 7):
    pts = sorted(points) + [target]
    fact, inv = build_factorials(target[0] + target[1], MOD)
    def C(a, b):
        return 0 if b < 0 or b > a else fact[a] * inv[b] % MOD * inv[a - b] % MOD
    def ways(p, q):                    # monotone routes from p to q
        dr, dc = q[0] - p[0], q[1] - p[1]
        return C(dr + dc, dr) if dr >= 0 and dc >= 0 else 0
    f = []
    for i, q in enumerate(pts):
        v = ways((0, 0), q)
        for j in range(i):
            v -= f[j] * ways(pts[j], q)
        f.append(v % MOD)
    return f[-1]

On the 4 by 5 example: f(1, 1) = 2 and f(2, 3) = 10 - 2 x 3 = 4. The target gets 35 - 2 x 10 - 4 x 2 = 7, matching the DP. The cost is O(k squared) for k obstacles plus factorial tables, regardless of grid size. Answers at this scale are astronomically large, so they are usually requested modulo a prime p. Then build_factorials precomputes factorials and their modular inverses via Fermat. When p is smaller than m + n, factorials hit zero, so switch to Lucas' theorem.

Sampling a route uniformly

Counts do more than answer how many. If you know the number of routes from every cell to the goal, you can draw a route uniformly at random. At each cell, move down with probability equal to the routes through the cell below divided by the routes from here, otherwise move right. Each step preserves uniformity, so every complete route has probability one over the total. This is how you generate unbiased test cases, estimate properties of a typical route by Monte Carlo, or build procedural maps with guaranteed reachability.

import random

def sample_path(grid, rng=random):
    """Uniformly random right/down route avoiding blocked cells, or None."""
    m, n = len(grid), len(grid[0])
    ways = [[0] * (n + 1) for _ in range(m + 1)]   # routes from (r, c) to the goal
    for r in range(m - 1, -1, -1):
        for c in range(n - 1, -1, -1):
            if grid[r][c]:
                ways[r][c] = 0
            elif (r, c) == (m - 1, n - 1):
                ways[r][c] = 1
            else:
                ways[r][c] = ways[r + 1][c] + ways[r][c + 1]
    if ways[0][0] == 0:
        return None
    r = c = 0
    moves = []
    while (r, c) != (m - 1, n - 1):
        if rng.randrange(ways[r][c]) < ways[r + 1][c]:
            moves.append("D"); r += 1
        else:
            moves.append("R"); c += 1
    return "".join(moves)

The table is filled backwards, from the goal, with a padding row and column of zeros so that edge cells need no special case. Drawing 70,000 samples on the 4 by 5 grid in one run gave each of its 7 routes between 9,891 and 10,167 times, against an expected 10,000. Using randrange on exact integers avoids the bias that floating-point ratios introduce once counts exceed 2 to the 53. The same suffix table also ranks and unranks routes in lexicographic order, which lets you shard an enumeration across workers by index range.

Variants

Operational guidance

• Decide the number type first. Exact big integers, 64-bit with a proven size bound, or modulo a prime. Write the choice into the function contract.
• Cross-check implementations. Test the DP against the closed form on every grid up to 20 by 20, and the inclusion-exclusion version against the obstacle DP on random small grids.
• Validate inputs. Zero or negative sizes, a blocked start or end, and ragged rows all need explicit handling.
• Avoid deep recursion. Memoised top-down code recurses about m + n deep. That is fine at 50 by 50 and hits Python's default limit of 1,000 frames once m + n nears 1,000.
• Count probabilities in log space. If you need the fraction of routes with a property, divide counts in floating point only after taking logs, or use exact fractions.

Failure modes

• Initialising the first row and column to 1 with obstacles present. Cells after a block in row 0 or column 0 must be 0.
• Off-by-one in the binomial. The answer is C(m + n - 2, m - 1), not C(m + n, m).
• Integer overflow in the closed form. It happens before the DP would overflow, as the side-32 row shows.
• Modulo applied inconsistently. Subtraction in inclusion-exclusion can go negative. Python's % always returns a non-negative result, so one reduction at the end works. In C or Java the remainder of a negative number is negative, so add MOD before reducing.
• Iterating the 1-D array right to left. Then dp[c - 1] still holds the old row, and the answer is wrong without any error.

Trade-offs

What to do next

1. Implement unique_paths and the closed form, and assert they agree for every m, n up to 20.
2. Port the closed form to a language with 64-bit integers and confirm it fails at side 32. Then fix it.
3. Run the obstacle DP and the inclusion-exclusion version on the 4 by 5 grid and get 7 from both.
4. Write build_factorials with Fermat inverses and count routes on a 100,000 by 100,000 grid with 200 random blocked cells modulo 1,000,000,007.
5. Add diagonal moves and check D(2, 2) = 13. Then try the on-or-below-diagonal variant and compare it with the Catalan numbers.