TL;DR
Grid-counting DP where each cell sums the cell above and to its left — O(m·n) time, O(n) space with a rolling row; or O(min(m,n)) via a binomial coefficient.
Approach 1 — Brute force recursion
From (i, j) the robot branches into “go down” and “go right”. Count paths that reach the goal.
def uniquePaths(m: int, n: int) -> int:
def paths(i: int, j: int) -> int:
if i == m - 1 and j == n - 1:
return 1
if i >= m or j >= n:
return 0
return paths(i + 1, j) + paths(i, j + 1)
return paths(0, 0)
Complexity: O(2^(m+n)) time — the recursion tree branches twice at nearly every cell. The 100×100 bound makes this hopeless, because the same cell is recomputed exponentially many times.
Approach 2 — Top-down memoization
The insight: the number of paths from (i, j) to the goal depends only on (i, j), not on how the robot got there. Cache each cell and the exponential tree collapses to O(m·n) distinct states.
State / recurrence. paths(i, j) = number of routes from cell (i, j) to (m-1, n-1). Transition paths(i, j) = paths(i+1, j) + paths(i, j+1); base case paths(m-1, n-1) = 1, and any out-of-grid cell returns 0.
from functools import lru_cache
def uniquePaths(m: int, n: int) -> int:
@lru_cache(maxsize=None)
def paths(i: int, j: int) -> int:
if i == m - 1 and j == n - 1:
return 1
if i >= m or j >= n:
return 0
return paths(i + 1, j) + paths(i, j + 1)
return paths(0, 0)
Complexity: O(m·n) time and space.
Approach 3 — Bottom-up tabulation (the 2-D table)
State / recurrence. dp[i][j] = number of paths from the start (0,0) to cell (i, j). The first row and first column are all 1 (only one straight-line route reaches them). For every interior cell:
dp[i][j] = dp[i-1][j] + dp[i][j-1]
def uniquePaths(m: int, n: int) -> int:
dp = [[1] * n for _ in range(m)]
for i in range(1, m):
for j in range(1, n):
dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
return dp[m - 1][n - 1]
Walkthrough with m = 3, n = 2. Initialize every cell to 1 (first row and column). Then dp[1][1] = dp[0][1] + dp[1][0] = 1 + 1 = 2, and dp[2][1] = dp[1][1] + dp[2][0] = 2 + 1 = 3. The bottom-right cell holds 3, matching the routes DDR, DRD, RDD.
Each arrow shows a cell feeding its right and down neighbors, so an interior cell’s value is the sum of the two arrows entering it:
flowchart LR
C00["(0,0)=1"] --> C01["(0,1)=1"]
C00 --> C10["(1,0)=1"]
C01 --> C11["(1,1)=2"]
C10 --> C11
C10 --> C20["(2,0)=1"]
C11 --> C21["(2,1)=3"]
C20 --> C21
Complexity: O(m·n) time, O(m·n) space.
Approach 4 — Space-optimized rolling row
The insight: row i only reads row i-1. Keep one array row of length n; when we do row[j] += row[j-1], the row[j] on the right still holds the old value (row above) and row[j-1] already holds the new value (cell to the left).
def uniquePaths(m: int, n: int) -> int:
row = [1] * n
for _ in range(1, m):
for j in range(1, n):
row[j] += row[j - 1]
return row[n - 1]
Complexity: O(m·n) time, O(n) space.
Approach 5 — Combinatorics
The insight: every valid path is a sequence of exactly m-1 down moves and n-1 right moves in some order. Choosing which of the m+n-2 positions are the downs fixes the path, so the answer is the binomial coefficient C(m+n-2, m-1).
from math import comb
def uniquePaths(m: int, n: int) -> int:
return comb(m + n - 2, m - 1)
Complexity: O(min(m, n)) time, O(1) space — the fastest of all, though the DP generalizes better when obstacles or weights appear.
Common pitfalls
- Off-by-one on the grid dimensions:
m is rows, n is columns, and the goal is (m-1, n-1).
- Starting the tabulation loops at 0 and overwriting the base row/column; the first row and column must stay
1.
- Reaching for the combinatorics formula and then being unable to adapt when a follow-up adds obstacles — the DP is the transferable skill.
Pattern takeaway
Grid DP where movement is monotone (only right/down) yields the archetypal recurrence dp[i][j] = dp[i-1][j] + dp[i][j-1]: a cell’s value is built from its already-computed top and left neighbors. Because a row depends only on the row above, these problems compress to a single rolling array. Recognize “count/optimize paths through a grid with restricted moves” and this table is your first move.