Climbing Stairs
Recognize the pattern
Brute force idea
The naive version of Climbing Stairs sounds like this: Recursive: try 1 step or 2 steps from each position — exponential. That direct path helps you understand the question, but it tends to treat every possibility as brand new instead of learning from earlier steps.
Better approach
The real unlock in Climbing Stairs comes when you notice this: DP: ways(n) = ways(n-1) + ways(n-2), like Fibonacci. Instead of recomputing the world every time, you preserve just enough context to let the next decision become obvious.
Key invariant
The compass for Climbing Stairs is this: The number of ways to reach step n equals the sum of ways to reach steps n-1 and n-2. As long as that statement keeps holding, you can trust the steps built on top of it.
Watch out for
The trap in Climbing Stairs usually looks like this: Using full array when only the last two values are needed — optimize space to. When the code becomes mechanical before the idea is clear, small edge cases start breaking the whole story.