Unique Paths

Difficulty: Medium

Problem

A robot stands on the top-left cell of an m × n grid and wants to reach the bottom-right corner. Its controls are humble: it can only move RIGHT or DOWN — never up, never left. Count the distinct routes it can take. This is the exact problem DP Foundations concept 8 (2D DP) previewed — your first table with two dimensions, now built for real. The headline example is a 3 × 7 grid (answer: 28); the walkthrough works on 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

  1. Define the 2D state: dp[r][c] = number of routes that reach cell (r, c)
  2. Case-split the last move: DOWN from above or RIGHT from the left → dp[r][c] = dp[r−1][c] + dp[r][c−1]
  3. Seed the bases on the edges: the first row and first column are all 1s
  4. Fill row by row, left to right — both ingredients are always already final
  5. 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