Pattern Recognition Drill
Easy Dynamic Programming
The Problem
You can climb 1 or 2 steps. How many distinct ways to climb n stairs?
What approach would you use?
Think about it before scrolling down.
dp[i] = dp[i-1] + dp[i-2]. Start: dp[0]=1, dp[1]=1. O(n) time, O(1) space with two variables.
Recursive with memoization. Same O(n) but uses O(n) stack space.
Common Trap
Recognize this IS Fibonacci. Don't overthink it.