Unique Paths
Unique Paths: A robot at the top-left of an m × n grid can only move right or down. How many distinct paths reach the bottom-right corner?
- 1 <= m, n <= 100
Intuition
Unique paths counts the routes from the top-left to the bottom-right of an m × n grid, moving only right or down.
The DP formulation is direct. Every cell is reached from above or from the left, and those are the only two ways in:
- dp[i][j] = dp[i-1][j] + dp[i][j-1], since each path into a cell arrives from exactly one of its two predecessors.
The first row and first column are all 1, because reaching any of those cells requires travelling in a straight line — there is exactly one way. Seeding them with 0 instead makes the entire grid zero, which is the standard bug.
Only the previous row is ever read, so the table collapses to a single array updated in place, giving O(n) space.
There is also a closed form, and it is worth seeing. Every path consists of exactly m − 1 down moves and n − 1 right moves in some order, so the count is the number of ways to arrange them:
C(m + n − 2, m − 1) — a single binomial coefficient, computable in O(min(m, n)).
That combinatorial view explains why the DP table holds Pascal's triangle rotated, which is a satisfying connection rather than a coincidence.
Computing the binomial naively overflows quickly through the factorials. Multiplying and dividing alternately keeps intermediate values small and avoids it.
Unique Paths II adds obstacles, which breaks the closed form entirely — blocked cells get 0 and the DP is then the only route.
The DP is O(m × n) time and O(n) space; the formula is O(min(m, n)) and O(1).
Grid DP announces itself when you can only move in directions that never revisit a cell — right and down here. That means a cell's answer depends purely on cells already computed, so a single sweep in reading order works with no recursion or memo table. If movement were allowed in all four directions the dependency would be cyclic and you'd need BFS instead.
Approach
Before reading on: price up what counting everything costs here, then ask what a single cell should mean, and which earlier cells it needs. Aim for O(m·n) time and O(m·n) space.
Identify the two predecessors
Every cell is reached only from above or from the left, so dp[i][j] = dp[i-1][j] + dp[i][j-1]. No other route exists.
Seed the edges with one
The first row and column are all 1 — reaching those cells requires a straight line. Seeding with 0 makes the entire grid zero.
Collapse to one row
Only the previous row is read, so a single array updated in place gives O(n) space with no change to the logic.
Know the closed form
Every path is m − 1 downs and n − 1 rights in some order, so the count is C(m + n − 2, m − 1) — computable in O(min(m, n)).
Avoid factorial overflow
Multiply and divide alternately when computing the binomial. Building the factorials first overflows well before the largest inputs.
Note where the formula breaks
Unique Paths II adds obstacles, which invalidates the combinatorial argument entirely — blocked cells get 0 and only the DP works.
Cost of the approaches
The DP is O(m × n) time with O(n) space; the formula is O(min(m, n)) with O(1) space.
Solution & live demo
Common pitfalls
Initialising the grid to zero
dp = [[0] * n for _ in range(m)]
dp = [[1] * n for _ in range(m)]
The first row and first column are reachable exactly one way each — you walk straight there. Zeros give them no paths to contribute, and the recurrence then propagates zero across the whole grid, returning 0 instead of the real count. Seeding everything to 1 sets both edges correctly in one line.
Starting the loops at 0
for i in range(m):
for j in range(n):
dp[i][j] = dp[i-1][j] + dp[i][j-1]for i in range(1, m):
for j in range(1, n):
dp[i][j] = dp[i-1][j] + dp[i][j-1]At i = 0, dp[i-1][j] is dp[-1][j] — Python wraps to the last row rather than erroring, so you silently read garbage from the far edge of the grid. The base row and column are already correct and must not be recomputed.
Edge cases
There is exactly one path (all rights or all downs); the all-ones edge initialization yields 1.
Start equals destination, so there is one trivial path — the single cell holds 1.
Values grow fast but stay within standard integer range for the constrained sizes; the DP avoids exponential recomputation.