Unique Paths

Signal

A grid where each cell's answer only depends on the cell above it and the cell to its left — that dependency shape (state = two indices, transition looks "up" and "left") is the 2-D DP fingerprint for path-counting problems.

Approach

Build a table where dp[i][j] is the number of ways to reach cell (i, j). The first row and first column can only be reached one way (a straight line of moves), so they're all 1. Every other cell's count is the sum of the ways to reach the cell above it and the cell to its left, since those are the only two moves that lead into it.

Skeleton

dp[0][*] = dp[*][0] = 1
for i in 1..m-1:
    for j in 1..n-1:
        dp[i][j] = dp[i-1][j] + dp[i][j-1]
return dp[m-1][n-1]

Solution

def unique_paths(m: int, n: int) -> int:
    prev_row = [1] * n
    for _ in range(1, m):
        curr_row = [1] * n
        for j in range(1, n):
            curr_row[j] = curr_row[j - 1] + prev_row[j]
        prev_row = curr_row
    return prev_row[-1]

Complexity

O(m · n) time — every cell is filled once. O(n) space by keeping only the previous row instead of the full 2-D table.

Pitfalls

• There's a closed-form answer, C(m + n - 2, m - 1) (choosing which moves are "down" among all moves) — correct and O(1) after computing a binomial coefficient, but many interviewers want to see the DP reasoning first.
• Forgetting to initialize the first row and first column to 1 — only doing one of them silently corrupts every cell that depends on the other edge.
• Allocating a full m x n table when only the previous row is ever read — fine for small grids, but worth naming the O(n) optimization if asked.