MediumBlind75MathDP
Unique Paths
There is a robot on an m x n grid. The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner. How many possible unique paths are there?
Examples
Input
m = 3, n = 2
Output
3
3 paths: right->down, down->right, down->right (from different start).
Input
m = 7, n = 3
Output
28
28 unique paths.
Constraints
- •
1 <= m, n <= 100
Approaches
Recursively try moving right or down.
CodeT: O(2^(m+n)) | S: O(m+n)
def unique_paths(m, n):
def helper(i, j):
if i == m - 1 and j == n - 1:
return 1
if i >= m or j >= n:
return 0
return helper(i + 1, j) + helper(i, j + 1)
return helper(0, 0)Use a 2D DP table to store number of paths to each cell.
CodeT: O(m * n) | S: O(m * n)
def unique_paths(m, n):
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]Use the formula C(m+n-2, m-1) = (m+n-2)! / ((m-1)! * (n-1)!).
Diagram
m=3, n=2
C(3, 2) = 3
Paths: RR, RD, DR
CodeT: O(min(m, n)) | S: O(1)
from math import comb
def unique_paths(m, n):
return comb(m + n - 2, m - 1)Complexity Comparison
| Approach | Time | Space | Description |
|---|---|---|---|
| Recursion | O(2^(m+n)) | O(m+n) | Recursively try moving right or down. |
| DP - 2D Array | O(m * n) | O(m * n) | Use a 2D DP table to store number of paths to each cell. |
| Math - Combinatorics | O(min(m, n)) | O(1) | Use the formula C(m+n-2, m-1) = (m+n-2)! / ((m-1)! * (n-1)!). |
Recursion
T: O(2^(m+n))S: O(m+n)
Recursively try moving right or down.
DP - 2D Array
T: O(m * n)S: O(m * n)
Use a 2D DP table to store number of paths to each cell.
Math - Combinatorics
T: O(min(m, n))S: O(1)
Use the formula C(m+n-2, m-1) = (m+n-2)! / ((m-1)! * (n-1)!).
Common Mistakes
Using recursion without memoization
Not initializing the DP table correctly
Forgetting that the first row and column should be all 1s