Unique paths in a grid (recursion)
Medium TimeO(2^(m+n)) naive; O(m·n) DP SpaceO(m + n) stack
A robot starts in the top-left cell of a grid and may move only right or down, never leaving it. Return how many distinct routes reach the bottom-right — a 3 × 3 grid has 6. A grid one cell wide, or one cell tall, has exactly one path.
Examples
Example 1
- Input
- m = 3n = 3
- Output
- Every route makes 2 moves right and 2 down, and there are 6 orders to make them in.
6
Example 2
- Input
- m = 1n = 5
- Output
- A single row, so the only route is straight along it with no choice anywhere.
1
The Code
function uniquePaths(m, n) {
if (m === 1 || n === 1) return 1;
return uniquePaths(m - 1, n) + uniquePaths(m, n - 1);
}
uniquePaths(3, 3);Done
More like this
All dynamic programming examples (20) →- Climbing stairs Count the ways to the top — Fibonacci in disguise.
- Coin change Try every coin and keep the cheapest way to make the amount.
- Max subarray One pass, two running totals — Kadane’s algorithm.
- LCS Match a character or drop one from either string.
- Edit distance Insert, delete, or replace — take the cheapest at each mismatch.
- 0/1 Knapsack For each item, take it or leave it — keep the more valuable branch.