Count distinct ways to climb n stairs taking 1 or 2 steps at a time.

Interview question: Climbing Stairs

You are climbing a staircase. It takes `n` steps to reach the top. Each time you can climb either `1` or `2` steps. In how many distinct ways can you climb to the top?

- At each move, you can climb either 1 step or 2 steps.
- To reach step `n`, the last move must come from step `n - 1` or step `n - 2`.
- Therefore, ways to reach `n` equals ways to reach `n - 1` plus ways to reach `n - 2`.

Understand the Choices

- For `n = 1`, there is 1 way: `1`.
- For `n = 2`, there are 2 ways: `1+1` and `2`.
- Every later answer is the sum of the previous two answers.

Recognize the Fibonacci Pattern

- A naive recursive solution branches into `n - 1` and `n - 2` repeatedly.
- That repeats the same calculations many times.
- Dynamic programming stores or carries forward the previous answers instead.

Avoid Recomputing Subproblems

- You do not need a full array because each state depends only on the previous two states.
- Let `one_back` represent ways to reach the previous step.
- Let `two_back` represent ways to reach the step before that.

Keep Only the Last Two Values

- Iterate from step 3 through step `n`, adding the last two counts each time.
- Time complexity is O(n).
- Space complexity is O(1) because only two counts are stored.