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