Unique Paths
Count grid routes from top-left to bottom-right moving only right or down. Every cell is reachable from the one above plus the one to its left.
- Category
- Dynamic Programming
- Time complexity
- O(m·n)
- Space complexity
- O(m·n)
Pseudocode
edges have exactly 1 path dp[r][c] = dp[r−1][c] + dp[r][c−1] answer at bottom-right
Reference implementation
for r in range(R):
for c in range(C):
if r == 0 or c == 0: dp[r][c] = 1
else: dp[r][c] = dp[r-1][c] + dp[r][c-1]