Unique Paths: Grid DP and the Rolling Row

If you interview at Google, Amazon, Bloomberg, expect some version of "Unique Paths". It is rated Medium, and it falls squarely into the Dynamic Programming pattern — pattern-first preparation beats grinding random problems every time. Part 5 of 11 in the Dynamic Programming arc.

The Problem

A robot starts at the top-left of an m x n grid, moves only right or down, and seeks the bottom-right corner. Count distinct paths. The gateway grid DP — the recurrence everyone can find, with the interview differentiation in the space optimization and the combinatorial aside.

Input:  m = 3, n = 7
Output: 28

Recognizing the Dynamic Programming Pattern

Dynamic programming is recursion with the repetition removed: define the answer to a subproblem, express it in terms of smaller subproblems, and compute each exactly once — top-down with memoization or bottom-up with a table. In interviews the grade hinges on the state definition said out loud ('dp[i] is the best answer using the first i items') far more than on the loop that follows. Most FAANG DP questions are one-dimensional or a small 2D grid — the nine below cover the shapes that repeat.

Every cell is entered from above or the left — disjoint cases, so paths(r, c) = paths(r−1, c) + paths(r, c−1) with edges seeded at 1. Grid counting with restricted moves is a 2D DP whose rows depend only on the previous row — the rolling-row cue.

The Approach

Process row by row into a single array: row[c] += row[c−1] sweeps left to right, where row[c] still holds the value from the row above (up-neighbor) and row[c−1] is already updated (left-neighbor). O(n) memory without changing the recurrence.

The closed form — choose which m−1 of the m+n−2 moves go down, comb(m+n−2, m−1) — is worth stating after the DP: the DP generalizes to obstacles and weights; the formula does not. That ordering shows judgment.

Python Solution

def unique_paths(m: int, n: int) -> int:
    """Distinct right/down paths across an m x n grid."""
    row = [1] * n
    for _ in range(1, m):
        for c in range(1, n):
            row[c] += row[c - 1]       # up-neighbor + left-neighbor
    return row[-1]

Complexity

• Time: O(m·n) — each cell computed once
• Space: O(n) — one rolling row

Interview Tips and Follow-Ups

• Narrate the rolling-row aliasing (which neighbor each term represents) — mangling that explanation under pressure is common and diagnostic.
• Unique Paths II adds obstacles: zero out blocked cells, seed carefully — the DP survives, the formula dies. That contrast is the lesson.
• Minimum Path Sum swaps plus for min over the same lattice — one recurrence family, three questions on the lists.

That wraps part 5 of the Dynamic Programming arc. The full Technical Interview category maps all one hundred questions to the nine patterns that dominate FAANG screens — work through an arc end to end and the next unseen variant will feel familiar.