Climbing Stairs

Product of Array Except Self

Count Vowels

Count ordered one-step and two-step paths to the top of a staircase.

A staircase has `n` steps. Starting below step 1, you may climb either 1 or 2 steps at a time. Return the number of distinct step sequences that reach exactly the top.

**Input / output**
- Input: `n: integer`
- Output: integer number of sequences

**Examples**
1. `n = 2` returns `2`: `1+1` and `2`.
2. `n = 5` returns `8`.

**Constraints**
- `1 <= n <= 45`

**Follow-up**
Show why this recurrence is Fibonacci-like and reduce the dynamic-programming table to two variables.

- 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.