Unique Paths
Problem
m x n board and wants to reach
the bottom-right cell. On every move it may step only one cell right or one cell
down. Return how many different routes lead from start to finish.m = 3, n = 7Output28m = 3, n = 2Output3 (R→D→D, D→R→D, D→D→R)1 ≤ m, n ≤ 100 · the answer is guaranteed to be ≤ 2 × 109
Try it yourself
class Solution {
public int uniquePaths(int m, int n) {
}
}
ways(r, c) = ways(r-1, c) + ways(r, c-1). Each row only
needs the row above it ⇒ one 1-D array is enough.Instinct Grid moves that never loop back (right/down, row to row) plus "count or optimise the paths" - build dp[r][c] from the cells that can step in.
Memory hack Every cell asks its parents - a cell's answer comes only from the neighbours that can move into it, so fill cells in the order they arrive.
Open the Grid DP guide →Approaches
Brute ForcePlain Recursion
O(2m+n)Space O(m + n)Count routes on an m x n board by peeling off the first move: going
down leaves an (m-1) x n board, going right leaves an
m x (n-1) board. A single row or column has exactly one route.
public int uniquePaths(int m, int n) { // A board with one row or one column has only a straight-line route if (m == 1 || n == 1) return 1; return uniquePaths(m - 1, n) + uniquePaths(m, n - 1); }
Correct and tiny, but recomputes the same sub-boards exponentially often.
Better2-D Tabulation
O(m · n)Space O(m · n)Store ways[r][c] for every cell. The first row and first column are
all 1; every other cell is the sum of its top and left neighbours.
Each cell is computed exactly once.
public int uniquePaths(int m, int n) { int[][] ways = new int[m][n]; for (int r = 0; r < m; r++) { for (int c = 0; c < n; c++) { if (r == 0 || c == 0) ways[r][c] = 1; // border cells: one straight route else ways[r][c] = ways[r - 1][c] + ways[r][c - 1]; } } return ways[m - 1][n - 1]; }
Polynomial and easy to explain, but keeps the whole grid in memory.
OptimalRolling 1-D Row
O(m · n)Space O(n)Keep a single array row. Before updating, row[c] still
holds the value from the row above; row[c-1] already holds the new value
to the left. So row[c] += row[c-1] applies the recurrence in place.
public int uniquePaths(int m, int n) { int[] row = new int[n]; Arrays.fill(row, 1); // first row: every cell reachable one way for (int r = 1; r < m; r++) { for (int c = 1; c < n; c++) { row[c] += row[c - 1]; // from above (old row[c]) + from the left } } return row[n - 1]; }
Dry runm = 3, n = 7
- r=01111111first row all 1
- r=11234567row[c] += row[c-1]
- r=213610152128canswer row[6] = 28
Same time as the table with only one row of memory — the expected answer.
m-1 downs among
m+n-2 moves, so the answer is C(m+n-2, m-1) — O(min(m,n))
with a long running product.At a glance
| Level | Approach | Time | Space |
|---|---|---|---|
| Brute Force | Plain Recursion | O(2m+n) | O(m + n) |
| Better | 2-D Tabulation | O(m · n) | O(m · n) |
| Optimal | Rolling 1-D Row | O(m · n) | O(n) |
- Mixing up the base case — a
1 x nboard has 1 route, notn. - Iterating the 1-D row right-to-left —
row[c-1]would still be the old value. - Computing the binomial with factorials — they overflow long before the answer does.
- Draw a 3 x 3 grid and fill the numbers; the Pascal-triangle shape makes the recurrence obvious.
- Show the recursion first, point at the repeated sub-boards, then tabulate.
- Offer the combinatorics formula as a bonus once the DP is done.