You can climb 1 or 2 steps at a time. How many distinct ways to reach the n-th step?
Spotting overlapping subproblems (it's Fibonacci) and rolling variables.
Ways(n) = Ways(n−1) + Ways(n−2): your last move was a 1-step or a 2-step. That's Fibonacci. Naive recursion recomputes the same values exponentially — cache them, or better, roll two variables for O(1) space. Recognizing the recurrence is the whole game. The three-part DP checklist lives here in miniature: state (ways to reach step i), transition (sum of the two reachable predecessors), and base cases (one way to stand at step 0, one way to reach step 1). Once you see 'the answer for n is built from a fixed number of smaller answers', top-down memoization and bottom-up tabulation are two spellings of the same idea.
'Count the ways to reach/build X' where each state depends on a few earlier states → DP.
Time O(n) · Space O(1)