Unique Paths: Counting Grid Routes with 2D Dynamic Programming
Solve LeetCode Unique Paths with dynamic programming — the grid recurrence, a worked walkthrough, JavaScript code, O(m*n) complexity, and the O(n) space trick.
This article has an interactive companion
Don't just read it — step through it interactively, one state change at a time.
A robot sits in the top-left corner of a grid. It can only step right or down, one cell at a time, and it needs to reach the bottom-right corner. How many distinct routes can it take?
That's Unique Paths, and it's the cleanest on-ramp to 2D dynamic programming you'll find. The whole problem collapses to a single idea: the number of ways to reach a cell is the number of ways to reach the cell above it plus the number of ways to reach the cell to its left. Once that clicks, the code writes itself — and the same grid-recurrence template reappears in edit distance, minimum path sum, and a dozen other interview staples.
The problem
Given two integers m (rows) and n (columns), count the unique paths a robot can take from the top-left cell (0, 0) to the bottom-right cell (m-1, n-1), moving only right or down.
Input: m = 3, n = 7
Output: 28
Input: m = 3, n = 3
Output: 6For the 3x3 case, every valid route is some ordering of exactly 2 "down" moves and 2 "right" moves. There are 6 such orderings, so 6 paths. That combinatorial view (more on it later) is a nice sanity check, but the DP approach is what generalizes when obstacles or weights get added.
The brute force baseline
The direct translation of the rules is recursion: to count paths reaching (i, j), count the paths reaching the cell above and the cell to the left, and add them. The origin is one path; stepping off the grid is zero.
function uniquePaths(m, n) {
function count(i, j) {
if (i === 0 && j === 0) return 1; // reached the start
if (i < 0 || j < 0) return 0; // walked off the grid
return count(i - 1, j) + count(i, j - 1);
}
return count(m - 1, n - 1);
}This is correct but brutally slow. The two recursive calls branch at every cell, and the same coordinates get recomputed over and over — count(1, 1) is recalculated by many different ancestors. The call tree grows roughly like 2^(m+n). For the modest 3x7 grid, a naive count balloons to over 180,000 recursive calls to produce the answer 28. The work is exponential because it never remembers anything.
The key insight
Every one of those repeated calls asks the exact same question and gets the exact same answer. The paths-to-(i, j) count doesn't depend on how you got there — only on the coordinates. That's the hallmark of an overlapping subproblem, and it means we can compute each cell's count once and store it.
Lay the answers out in a grid dp, where dp[i][j] = number of unique paths from (0, 0) to (i, j). Two facts seed it:
- Top row (
dp[0][j]): only one way to get there — move right the whole time. So every cell is1. - Left column (
dp[i][0]): only one way — move down the whole time. Also1.
Every interior cell then follows the recurrence, because a path into (i, j) must arrive either from above or from the left, and those two sets of paths never overlap:
dp[i][j] = dp[i-1][j] + dp[i][j-1]Fill the grid top-to-bottom, left-to-right, and by the time you reach dp[m-1][n-1] every value it needs is already computed.
The optimal solution
Here's the bottom-up tabulation, exactly as the visualizer runs it. Initialize the borders to 1, then sweep the interior applying the recurrence.
var uniquePaths = function(m, n) {
let dp = Array.from({ length: m }, () => Array(n).fill(0));
for (let i = 0; i < m; i++) dp[i][0] = 1;
for (let j = 0; j < n; j++) dp[0][j] = 1;
for (let i = 1; i < m; i++) {
for (let j = 1; j < n; j++) {
dp[i][j] = dp[i-1][j] + dp[i][j-1];
}
}
return dp[m-1][n-1];
};No recursion, no repeated work — each of the m*n cells is written exactly once, reading two neighbors that are already final.
Notice a detail in the recurrence: when you compute row i, the only prior row you ever read is row i-1. You never look two rows back. That means you don't need the whole 2D table — a single row (plus the value being built) is enough. Rolling one row forward drops the space from O(m*n) to O(n):
var uniquePaths = function(m, n) {
let dp = new Array(n).fill(1); // top row is all 1s
for (let i = 1; i < m; i++) {
for (let j = 1; j < n; j++) {
dp[j] = dp[j] + dp[j - 1]; // (from top) + (from left)
}
}
return dp[n - 1];
};In that one-line update, dp[j] on the right still holds the value from the row above (the "top" neighbor) before it gets overwritten, and dp[j-1] is the freshly computed cell to its left. This is the rolling-array view the visualizer animates as two stacked rows.
Walkthrough
Trace the full 2D version on m = 3, n = 3. First the borders are seeded to 1; then the four interior cells fill in, each summing its top and left neighbors.
| Cell (i, j) | Top neighbor | Left neighbor | New value = top + left |
|---|---|---|---|
| (1, 1) | dp[0][1] = 1 | dp[1][0] = 1 | 1 + 1 = 2 |
| (1, 2) | dp[0][2] = 1 | dp[1][1] = 2 | 1 + 2 = 3 |
| (2, 1) | dp[1][1] = 2 | dp[2][0] = 1 | 2 + 1 = 3 |
| (2, 2) | dp[1][2] = 3 | dp[2][1] = 3 | 3 + 3 = 6 |
The final grid looks like this, with the answer sitting in the bottom-right:
1 1 1
1 2 3
1 3 6 ← dp[2][2] = 6 unique pathsEvery interior number is literally the sum of the number above it and the number to its left. If that pattern looks familiar, it's Pascal's triangle rotated 45 degrees — which is exactly why the closed-form answer is a binomial coefficient.
Complexity
| Approach | Time | Space | Why |
|---|---|---|---|
| Naive recursion | O(2^(m+n)) | O(m+n) | every cell re-expands its whole subtree; only the call stack is stored |
| 2D tabulation | O(m*n) | O(m*n) | fill each cell once; keep the full table |
| Rolling array | O(m*n) | O(n) | fill each cell once; keep only one row |
| Combinatorics | O(min(m, n)) | O(1) | compute C(m+n-2, m-1) directly |
The DP versions do constant work per cell across an m by n grid, so time is O(m*n) either way. The only lever is space: the rolling array proves you never need more than one row in memory.
Common mistakes
- Forgetting to seed both borders. If the top row or left column isn't initialized to
1, the interior recurrence reads zeros and every count comes out wrong. The base case is the algorithm here. - Iterating the interior from index 0. The recurrence
dp[i][j] = dp[i-1][j] + dp[i][j-1]only applies to cells that have a top and left neighbor. Start both interior loops at1; the border cells are already set. - Overwriting in the wrong order in the rolling version.
dp[j] = dp[j] + dp[j-1]only works because you sweepjleft-to-right, sodp[j-1]is already this row's value whiledp[j]is still last row's. Reverse the direction and you'd read a stale left neighbor. - Reaching for 64-bit worries too early. Path counts grow fast, but for the standard constraints (
m, n <= 100) the answer stays within a safe integer range — no overflow handling needed in JavaScript.
Where this pattern shows up next
The "fill a table where each cell is a small combination of already-solved neighbors" template is the backbone of grid and sequence DP. Once Unique Paths clicks, these are the natural next steps:
- Word Break — 1D DP over a string, where each position depends on earlier positions instead of a grid neighbor.
- Longest Increasing Subsequence — build each answer from all valid earlier states, the sequence cousin of this recurrence.
- Partition Equal Subset Sum — a subset-sum table that fills the same way, one reachable value at a time.
- Coin Change II — counts combinations with a 2D DP that mirrors Unique Paths almost exactly.
You can also step through the Unique Paths visualizer to watch the grid fill cell by cell, and flip between the bottom-up rolling array and the top-down memoized recursion side by side.
FAQ
What is the time and space complexity of Unique Paths?
The dynamic programming solution runs in O(m*n) time because it computes each of the m by n grid cells exactly once, doing constant work (one addition) per cell. Space is O(m*n) if you keep the full table, but you can reduce it to O(n) by rolling a single row forward, since each cell only depends on the value directly above it and directly to its left.
Why do the top row and left column start at 1?
Because there's exactly one way to reach any cell in the top row — move right the entire time — and exactly one way to reach any cell in the left column — move down the entire time. The robot has no other option along the edges, so each of those cells has a path count of 1. These border values are the base cases that seed the interior recurrence.
Can Unique Paths be solved without dynamic programming?
Yes. Any path from top-left to bottom-right consists of exactly m-1 down moves and n-1 right moves in some order, so the answer is the binomial coefficient C(m+n-2, m-1). That closed-form runs in O(min(m, n)) time and O(1) space. It's faster, but the DP approach is the one worth mastering because it extends to variants — obstacles, weighted grids, blocked cells — where no clean formula exists.
How is this different from Unique Paths II?
Unique Paths II adds obstacles: some cells are blocked and can't be stepped on. The DP structure is identical, but any blocked cell gets a path count of 0 instead of summing its neighbors, and the border seeding stops the moment it hits an obstacle. Because there's no longer a clean combinatorial formula, the DP table becomes the only practical approach — which is exactly why learning the tabulation here pays off.
Make it stick: run this one yourself
Don't just read it — step through it interactively, one state change at a time.