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?
Intuition
The number of ways to reach a cell equals the ways to reach the cell above plus the ways to reach the cell to its left — the only two moves that land there. Fill the grid and the answer is the bottom-right cell.
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
The recursive count, and why it's slow
Since the robot only moves right or down, the number of ways to reach a cell is the ways to reach the cell above it plus the ways to reach the cell to its left: paths(i,j) = paths(i-1,j) + paths(i,j-1). Written as plain recursion this is correct but exponential — the same sub-cells get recomputed over and over. The recurrence is begging to be cached.
Fill a table bottom-up instead
Every cell's answer depends only on cells above and to the left — cells we can compute first. So build a DP table and fill it in order. The base cases are the top row and left column: there's exactly one straight-line path along an edge (all rights, or all downs), so initialize them to 1. Every interior cell then becomes the sum of its top and left neighbors, each already filled.
Read off the corner
Sweep the interior with dp[i][j] = dp[i-1][j] + dp[i][j-1]; the bottom-right cell holds the total number of paths. Each of the m·n cells is computed once, so it's O(m·n) time. Since each row only needs the row above it, you can compress the table to a single rolling row for O(n) space — but the full grid is clearest to read.
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.