Unique Paths

Unique Paths is the gentlest two-index DP. The state is a cell, the choices are "came from above" or "came from the left", and the table is the grid — you can see it fill in.

It is the model for every grid DP that follows: minimum path sum, paths with obstacles, largest square of 1s.

The problem

A robot stands in the top-left cell of a grid with m rows and n columns. It can move only right or down, one cell at a time. Return the number of different paths to the bottom-right cell.

• m = 3, n = 4 → 10. Every path is 3 rights and 2 downs in some order.
• m = 3, n = 3 → 6: RRDD, RDRD, RDDR, DRRD, DRDR, DDRR.
• m = 1, n = 5 → 1. One straight line.

Constraints: 1 ≤ m, n ≤ 100.

Clarifying questions

• Only right and down? Yes. No up, left or diagonal.
• Any blocked cells? Not here. Blocked cells are the first follow-up.
• Does a 1 × 1 grid count as one path? Yes — the robot is already there.

Approach 1: the simple way — follow every path

Count paths into cell (r, c) by asking where the robot came from: the cell above or the cell to the left. Recurse until you hit the top row or the left column, where there is only one way in.

1def paths_rec(m: int, n: int) -> int:2    """Count paths by recursing on where the last move came from."""3    def count(r: int, c: int) -> int:4        if r == 0 or c == 0:5            return 1                     # top row or left column: one straight path6        return count(r - 1, c) + count(r, c - 1)7    return count(m - 1, n - 1)

Why it is too slow. The recursion makes a call for every path prefix it follows, so the work grows with the answer itself. A 10 × 10 grid takes 97,239 calls; a 16 × 16 grid takes 310,235,039. At 100 × 100 the answer itself has 59 digits. But there are only m × n different cells, so nearly every call repeats one already made.

The key insight

Every path into cell (r, c) arrives through exactly one of two doors: from (r − 1, c) above, or from (r, c − 1) on the left. The two groups never overlap — the last move differs — and together they are all the paths. So you add the two counts:

dp[r][c] = dp[r - 1][c] + dp[r][c - 1]dp[0][c] = 1 and dp[r][0] = 1   (the edges: only one straight path)

The state is dp[r][c] = the number of paths from the start to cell (r, c). It is a count, so the combine step is +. That "count adds, best-value takes max or min" rule is the one thing to check first in every DP transition.

Approach 2: memoisation

1from functools import cache23def paths_memo(m: int, n: int) -> int:4    @cache5    def count(r: int, c: int) -> int:6        if r == 0 or c == 0:7            return 18        return count(r - 1, c) + count(r, c - 1)9    return count(m - 1, n - 1)

m × n states, each computed once: O(m × n) time and space, plus a stack up to m + n deep.

Approach 3: tabulation

1def paths_table(m: int, n: int) -> int:2    """dp[r][c] = number of paths from the start to (r, c)."""3    dp = [[1] * n for _ in range(m)]     # first row and first column: one way4    for r in range(1, m):5        for c in range(1, n):6            dp[r][c] = dp[r - 1][c] + dp[r][c - 1]   # from above + from the left7    return dp[m - 1][n - 1]

Row by row, left to right, so both cells a rule reads are already filled. For m = 3, n = 4:

1   1   1   11   2   3   41   3   6  10

Each cell is the sum of the one above and the one to its left. The bottom-right cell holds 10.

Approach 4: one row

Row r reads only row r − 1. Better still, you can update a single row in place: before the update, row[c] still holds the value from the row above; row[c − 1] has just been updated to the current row. That is exactly "above + left".

1def unique_paths(m: int, n: int) -> int:2    """Grid paths with one row of memory."""3    row = [1] * n                        # the top row4    for _ in range(1, m):5        for c in range(1, n):6            row[c] += row[c - 1]         # old row[c] is "above", row[c-1] is "left"7    return row[-1]

Dry run for m = 3, n = 4:

The same numbers as the full table, one row at a time. Complexity: O(m × n) time, O(n) space. Loop over the shorter side on the inside for O(min(m, n)).

Approach 5: count with combinations

Every path is a string of m − 1 downs and n − 1 rights, in any order. So the number of paths is the number of ways to choose where the downs go among m + n − 2 moves: C(m + n − 2, m − 1). For m = 3, n = 4 that is C(5, 2) = 10. In Python, math.comb(m + n - 2, m - 1) gives it in O(min(m, n)) steps. It is a lovely answer to mention — but the DP is the one that survives the follow-ups, because a blocked cell breaks the formula.

Edge cases

• One row or one column — the loops do not run; the answer is 1.
• 1 × 1 grid — row = [1], answer 1.
• Large grids — the answer grows very fast: C(198, 99), a 59-digit number, for 100 × 100. Python integers never overflow; in Java or C++, say which type you would use or ask whether the answer is taken modulo a prime.

Follow-ups

• Some cells are blocked — set the count of a blocked cell to 0 and leave the rest of the rule alone. The top row is no longer all 1s: a block cuts off everything to its right. With one block at (1, 1) in the 3 × 4 grid, the answer drops from 10 to 4.
• Each cell has a cost; find the cheapest path (Minimum Path Sum) — same table, but min of the two neighbours plus the cell's cost.
• Robot may also move diagonally — add a third door: dp[r - 1][c - 1]. In the one-row version, keep the old value of row[c - 1] in a variable before overwriting it.