LeetCode 70 Climbing Stairs - Recursive Intuition

Think about this recursively. To reach step $n$, you must have come from either step $n-1$ (one step) or step $n-2$ (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.