Unique Paths

Difficulty: Medium

Problem

A cleaning robot starts in the top-left cell of an m × n grid and must finish in the bottom-right cell. It can only step RIGHT or DOWN, never back up or to the left. Return how many different paths lead from start to finish. This is the first real two-dimensional DP table, the one DP Foundations concept 8 (2D DP) previewed. The headline example is a 3 × 7 grid; the walkthrough uses a smaller 3 × 4 grid whose answer is 10, so every cell fits on screen.

Example

Input: m = 3, n = 7
Output: 28
Explanation: Every route is some shuffle of exactly 2 down-moves and 6 right-moves, 28 distinct orderings. On the walkthrough's 3 × 4 grid, the same counting gives 10.

Brute-force approach

No separate brute-force phase: the naive recursion, its route-sized explosion, and both DP cures form one arc inside the guided lesson.

Optimal approach

Key insight: Every route into a cell arrives from above or from the left, two disjoint groups that ADD. Fill the table row by row and the corner collects all 28 routes.

Run the full DP arc from the foundations: the natural last-move recursion, the memo keyed by the pair (r, c), and the 2D table filled row by row, closing with the rolling-row trick that shrinks space to a single row.

Steps

Define the 2D state: dp[r][c] = number of routes that reach cell (r, c)
Case-split the last move: DOWN from above or RIGHT from the left → dp[r][c] = dp[r−1][c] + dp[r][c−1]
Seed the bases on the edges: the first row and first column are all 1s
Fill row by row, left to right. Both ingredients are always already final
Read the answer at the bottom-right corner; keep one rolling row for O(n) space

Time complexity: O(m × n) · Space complexity: O(n) with a rolling row

Pseudocode

function uniquePaths(m, n):
    // dp[r][c] = number of routes that reach cell (r, c)
    dp = m x n table, every cell = ____    // edges: one straight route each

    for r in 1 .. m-1:
        for c in 1 .. n-1:
            // last move was DOWN or RIGHT - disjoint groups ADD
            dp[r][c] = dp[____][c] + dp[r][____]

    return dp[____][____]

Hints

Every cell starts at the edge value: how many routes reach a cell on the top row or the left column? That single number seeds the whole table: the loops then fix the interior.
One ingredient counts the routes whose last move was DOWN. They were standing directly ABOVE, which row is that?
The other ingredient counts the routes whose last move was RIGHT. They were standing just to the LEFT, which column is that?
The robot finishes at the bottom-right cell. With 0-based indexes on an m × n table, which row and column hold the final answer?

Complexity questions

How much work does the naive recursion do?

Exponential: the call tree sprouts one leaf per ROUTE, and routes number C(m+n−2, m−1) (28 already for 3×7, ~40 million for 15×15). Each complete route corresponds to a leaf of the call tree, so the leaves alone number C(m+n−2, m−1): a binomial that explodes as the grid grows. All that effort re-derives just m×n distinct answers, which is the overlap DP eliminates.

What are the complexities of the tabulated solution?

O(m·n) time and O(m·n) space. Constant work per cell, one full table. Each of the m·n cells is filled exactly once, from two already-final neighbors. Constant work per cell, so O(m·n) time. The full table costs O(m·n) memory... which the next question shrinks.

Why does ONE reusable row suffice to replace the whole table?

The transition reads only the previous row (dp[r−1][c]) and the current row's left neighbor (dp[r][c−1]). Rows further back are never touched again. Concept 9's audit: check how far back the transition reaches. Up-neighbor = previous row; left-neighbor = current row, already updated. So row[c] += row[c-1] works in place, at that instant row[c] still holds the old row's value (up) while row[c-1] is fresh (left). One length-n array forever: O(n).

Now some cells contain obstacles the robot can't enter. What changes in your solution?

Blocked cells simply get dp = 0 (zero routes stand there); every other line is identical: that's LeetCode's Unique Paths II, now trivial for you. This is why the table beats the closed-form formula: the formula dies the moment the grid isn't pristine, but the DP just writes 0 in blocked cells and keeps summing. No route may pass through nothing. One care point: an obstacle on the first row or column blocks every edge cell after it, so the edges stop being all 1s.

Check your understanding of Unique Paths

Climbing Stairs described a subproblem with ONE number (the step index). Why does Unique Paths need TWO?

The robot's situation is a grid position, a row AND a column. 'I'm at step 7' means nothing on a grid; only the pair (r, c) pins it down, so the state is 2D. Straight from DP Foundations concept 8: when one index can't describe a subproblem, use two. dp[r][c] = the number of routes that reach cell (r, c). The framework (state, transition, base) is unchanged; only the table gained a dimension.

The robot is standing on cell (r, c). How did it get there, what was its LAST move?

Either a DOWN move from (r−1, c) above, or a RIGHT move from (r, c−1) on the left. There is no third way, so dp[r][c] = dp[r−1][c] + dp[r][c−1]. The last-step trick from the foundations, now in 2D. With only right/down moves allowed, every route into (r, c) finishes with exactly one of two hops: down from above, or right from the left. The two groups share no routes, so counting the whole means ADDING the parts.

What are the base cases, and where do they live in the 2D table?

The entire first row and first column are 1, each edge cell has exactly one straight-line route, so the bases live on the table's EDGES. A top-row cell can only be reached by marching right the whole way; a first-column cell only by marching straight down. One route each. In 1D the bases were the first slot or two; in 2D they stretch along the edges: a full row and a full column of free answers.

In what order do we fill the table, and why does that order never break?

Row by row, left to right. Each cell needs its up-neighbor (previous row) and left-neighbor (this row, one step behind), and row-major order guarantees both are already filled. The tabulation invariant: every ingredient must already be in the table when you reach for it. dp[r][c] reads one cell from the finished previous row and one cell just behind it in the current row: row-major order satisfies both dependencies at every single cell.

Warm-up trace: on a tiny 2 × 2 grid, how many distinct routes are there?

2: right-then-down, or down-then-right. Trace it with a finger: RIGHT then DOWN, or DOWN then RIGHT. Two routes, and the table agrees: the edges seed as 1s, then dp[1][1] = dp[0][1] + dp[1][0] = 1 + 1 = 2. When the formula matches your finger-trace, you're ready to code.