Unique Paths
LeetCode 62 • Medium • Dynamic Programming
m×n grid, start (0,0), end (m-1,n-1). Move only right or down. dp[i][j]=dp[i-1][j]+dp[i][j-1]. m=3, n=7 → 28.
TimeO(m×n)fill table
SpaceO(m×n)DP table
Current: —
Result: —
Ready
Press Play. dp[i][j] = paths to (i,j). dp[i][j] = dp[i-1][j] + dp[i][j-1]. First row/col = 1.
TimeO(m×n)memoized
SpaceO(m×n)memo + call stack
Recursive: paths(i,j) — base i=0 or j=0 return 1; if (i,j) in memo return memo; memo[(i,j)] = paths(i-1,j) + paths(i,j-1); return memo[(i,j)].
Practice until you don't need to look. The green highlights are the nuances to burn into memory.
PATTERN ▸ dp[i][j] = dp[i-1][j] + dp[i][j-1] O(m×n) · O(m×n)
① INIT
dp = [[0]*n for _ in range(m)]
② BASE (first row & col = 1)
for i in range(m): dp[i][0] = 1
for j in range(n): dp[0][j] = 1
③ FILL
for i in range(1, m):
for j in range(1, n):
dp[i][j] = dp[i-1][j] + dp[i][j-1]
④ RETURN
return dp[m-1][n-1]
▼ your implementation ▼
Verify your solution: