Unique Paths LeetCode Solution: Complete DP Walkthrough

Unique Paths (LeetCode #62) is the first 2D dynamic programming problem most engineers encounter, and for good reason. It strips away all the noise — no weights, no obstacles, no tricky constraints — and hands you the purest possible grid DP setup. If you can solve this, you have the mental model for dozens of harder problems.

The unique paths leetcode problem asks a deceptively simple question: given an m x n grid, how many distinct paths can a robot take from the top-left corner to the bottom-right corner if it can only move right or down? The answer introduces you to the core idea behind every grid DP problem — building solutions from smaller overlapping subproblems.

This walkthrough covers three approaches: the standard 2D DP table, the space-optimized single-row version, and the mathematical combinatorics solution. By the end, you will understand not just how to solve LeetCode 62 but why the grid DP pattern works the way it does.

You are given two integers m and n representing the dimensions of a grid. A robot starts at position (0, 0) — the top-left cell — and wants to reach position (m-1, n-1) — the bottom-right cell. At every step, the robot can only move one cell to the right or one cell down. The question is: how many unique paths exist from start to finish?

The constraints are generous: 1 <= m, n <= 100. This means a brute-force recursive solution that explores every path will time out badly — there are C(m+n-2, m-1) total paths, which grows combinatorially. For a 23 x 12 grid, that is over 7 million paths. You need dynamic programming.

The key insight is that each cell can only be reached from the cell directly above it or the cell directly to its left. That means the number of ways to reach any cell equals the sum of the ways to reach those two neighbors. This is the recurrence relation, and it is the entire foundation of the solution.

The standard unique paths dp solution builds a 2D table where dp[i][j] represents the number of ways to reach cell (i, j). The recurrence is straightforward: dp[i][j] = dp[i-1][j] + dp[i][j-1]. The cell above contributes all paths that arrived by moving down, and the cell to the left contributes all paths that arrived by moving right.

The base cases are equally simple. The entire first row has exactly one path to each cell — you can only get there by moving right repeatedly. The entire first column also has exactly one path — you can only get there by moving down. So dp[0][j] = 1 for all j, and dp[i][0] = 1 for all i.

Fill the table row by row, left to right, and the answer sits in dp[m-1][n-1]. The time complexity is O(m * n) because you visit every cell once. The space complexity is also O(m * n) for the full table. This is the leetcode 62 solution that interviewers expect to see first — clear, correct, and easy to reason about.

For a 3 x 7 grid, the table fills out to dp[2][6] = 28. You can verify this by hand for small grids: a 2 x 2 grid has 2 paths, a 2 x 3 grid has 3 paths, and a 3 x 3 grid has 6 paths. The pattern is unmistakable — and it is exactly the Pascal triangle rotated 45 degrees.

The 2D table works, but you can do better on space. Look at the recurrence again: dp[i][j] depends only on dp[i-1][j] (the cell directly above, which is the same column in the previous row) and dp[i][j-1] (the cell to the left, which you just computed). You never look back more than one row.

This means you can collapse the entire 2D table into a single 1D array of length n. Initialize every element to 1 (representing the first row). Then for each subsequent row, iterate left to right and update: dp[j] += dp[j-1]. The old dp[j] value is the "cell above" and dp[j-1] is the "cell to the left" — exactly what the recurrence needs.

The unique paths bottom up approach with this optimization runs in O(m * n) time but only O(min(m, n)) space. If m < n, transpose the problem and iterate over the shorter dimension. This is the version that impresses interviewers because it shows you understand DP space optimization as a general technique, not just a trick for this problem.

There is a pure math solution to this grid dp problem that runs in O(m + n) time and O(1) space. The robot must make exactly (m - 1) down moves and (n - 1) right moves, for a total of (m + n - 2) moves. The number of unique paths is the number of ways to choose which moves are "down" — that is C(m + n - 2, m - 1), the binomial coefficient.

For a 3 x 7 grid: C(3 + 7 - 2, 3 - 1) = C(8, 2) = 28. This matches the DP result exactly. You can compute this iteratively to avoid overflow: multiply and divide step by step rather than computing factorials directly.

While the combinatorics grid approach is elegant, it is harder to derive under interview pressure and does not generalize to variations like Unique Paths II (with obstacles) or Minimum Path Sum. Present the DP solution first, then mention the math as a bonus. Interviewers will appreciate that you know both approaches.

The simplest edge case is a 1 x 1 grid — the robot is already at the destination, so the answer is 1. A 1 x n or m x 1 grid also has exactly one path because you can only move in a single direction. Your base case initialization handles both of these automatically.

Unique Paths II (LeetCode #63) adds obstacles to the grid. Cells marked as obstacles have dp[i][j] = 0 instead of the sum formula, and if the start or end cell is blocked the answer is zero. The recurrence is identical otherwise — this is why mastering the clean version of unique paths explained here matters so much.

Other problems that build directly on this grid DP pattern include Minimum Path Sum (#64), where you replace counting with minimizing, Triangle (#120), which uses a triangular grid, and Dungeon Game (#174), which requires processing from bottom-right to top-left. The unique paths dp pattern is the seed for all of them.

Unique Paths is not just another Medium problem to check off — it is the mental model for an entire family of grid-based dynamic programming questions. Once you internalize the pattern of building a table where each cell depends on its neighbors, you can adapt it to weighted paths, obstacles, multi-dimensional grids, and path-counting with constraints.

The progression from brute-force recursion to memoization to bottom-up tabulation to space optimization is the same progression you will use for every DP problem. Unique Paths makes that progression visible because the problem is simple enough that you can focus entirely on the technique rather than getting lost in complex constraints.

Practice this problem until the recurrence is automatic, then move on to Unique Paths II, Minimum Path Sum, and Dungeon Game. Use YeetCode flashcards to drill the grid DP pattern and its variations so you can recognize and apply it instantly when it appears in your next interview.