This is LeetCode #62: Unique Paths — a classic 2D DP problem! 🤖
💡 Think of it like this: A robot sits at the top-left corner of a grid. It can only move right or down. How many different routes can it take to reach the bottom-right corner?
The DP Insight: To reach cell (r, c), the robot came from either above (r-1, c) or from the left (r, c-1).
dp[r][c] = dp[r-1][c] + dp[r][c-1]
💭 Challenge time! Now implement this yourself using the strategy above. The best way to learn is by doing! ⭐
Complexity: Time O(m × n), Space O(n) with optimization (just one row instead of full grid). Fun fact: The answer is also the combinatorial formula C(m+n-2, m-1)!
# For a 3×7 grid:
# 1 1 1 1 1 1 1
# 1 2 3 4 5 6 7
# 1 3 6 10 15 21 28 ← answer is 28!
def uniquePaths(m, n):
dp = [1] * n # First row: all 1s
for r in range(1, m): # Each subsequent row
for c in range(1, n):
dp[c] += dp[c-1] # dp[c] = above + left
return dp[-1]
uniquePaths(3, 7)
28