Climbing Stairs
You are climbing a staircase that has n steps. Every move, you may climb either 1 step or 2 steps. Count how many distinct sequences of moves get you from the bottom to the top.
Two sequences are different if the order of moves differs — climbing 1 then 2 is not the same as 2 then 1.
Constraints: 1 <= n <= 45, so the answer fits in a regular integer.
Examples
- Input:
- n = 2
- Output:
- 2
Two ways: (1 step + 1 step) or (2 steps).
- Input:
- n = 3
- Output:
- 3
Three ways: (1+1+1), (1+2), (2+1).
- Input:
- n = 5
- Output:
- 8
The counts follow the Fibonacci sequence: 1, 2, 3, 5, 8, ...
Hints
One at a time — struggle first, peek second.
Your thinking space — verify on LeetCode, then mark it.