Unique Paths: From Grid DP to a Single Binomial Coefficient

Unique Paths counts the ways a robot can move from the top-left to the bottom-right of an m x n grid, moving only right or down. It is a good problem to show three levels of solution in one answer.

Level 1: 2D DP

Each cell can be reached from the cell above or the cell to the left, so dp[r][c] = dp[r-1][c] + dp[r][c-1], with the first row and column equal to 1.

Level 2: one row

Only the previous row is ever read, so keep a single array and update it left to right.

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

Level 3: combinatorics

Every path is a sequence of m-1 downs and n-1 rights, so the answer is C(m+n-2, m-1). In Python, math.comb(m + n - 2, m - 1) returns it exactly. Mention overflow if the interviewer wants a fixed-width language and compute the product incrementally, dividing as you go.

Follow-ups

Unique Paths II adds obstacles: set dp to 0 on blocked cells and the formula no longer applies. Minimum Path Sum keeps the same shape with min instead of plus. Saying which follow-ups break the closed form shows depth.

If you want prompts while practising multi-level answers, try the interview copilot app we build at Linkjob AI. Disclosure: I help build Linkjob AI.

Edit

Pub: 02 Nov 2026 19:58 UTC

Views: 7