Climbing Stairs

Intuition

To land on step n your final move is either a single step from step n-1 or a double step from step n-2. Every distinct way of reaching n therefore decomposes uniquely into a way of reaching one of those two predecessors, so ways(n) = ways(n-1) + ways(n-2). That is exactly the Fibonacci recurrence, with base cases ways(1) = 1 and ways(2) = 2. Because each value depends only on the two immediately before it, there is no need to store the whole table. We can walk upward while carrying just the previous two counts, updating them on every iteration. This collapses the memory footprint to a constant while keeping a single linear pass.

Algorithm walkthrough

1. 1Handle the tiny cases directly: when n is 1 or 2 the answer is simply n.
2. 2Initialize prev = 1 (ways to reach step 1) and curr = 2 (ways to reach step 2).
3. 3Iterate i from 3 up to n, treating curr as ways(i-1) and prev as ways(i-2).
4. 4At each step compute next = prev + curr, then shift the window: prev becomes curr and curr becomes next.
5. 5When the loop finishes, curr holds ways(n).
6. 6Return curr as the number of distinct ways.