Think about this recursively. To reach step , you must have come from either step (one step) or step (two steps). So: - ways(n) = ways(n-1) + ways(n-2). - Base cases: ways(1) = 1 (one way), ways(2) = 2. This is exactly the Fibonacci recurrence! Climbing stairs is Fibonacci in disguise, just with different starting values.
Here's the pattern: many DP (dynamic programming) problems are just Fibonacci wearing a costume. Once you see through the disguise, the solution writes itself. Let's see how many disguises you can see.