70. Climbing Stairs
You stand at the bottom of a staircase with n steps. Each move carries you up either one step or two steps.
Count how many distinct sequences of moves take you from the ground to the top, and return that count.
Two climbs are different whenever their move sequences differ anywhere along the way: 1+2 and 2+1 both reach step 3, but they are separate climbs.
Example 1:
Input: n = 3
Output: 3
Explanation: Three sequences reach step 3: 1+1+1, 1+2, and 2+1.
Example 2:
Input: n = 5
Output: 8
Explanation: The counts build on each other: 1, 2, 3, 5, 8 for n = 1..5 — every climb to step 5 arrives from step 4 (5 ways) or step 3 (3 ways).
Constraints:
- 1 ≤ n ≤ 45
Hints:
Think about the very last move of any climb that ends on step n: it came either from step n−1 (a +1 move) or from step n−2 (a +2 move). Those two groups cover every climb and never overlap.
So ways(n) = ways(n−1) + ways(n−2) with ways(1) = 1 and ways(2) = 2 — the Fibonacci recurrence. Plain recursion recomputes the same values exponentially many times; either cache the results or build the sequence bottom-up with two rolling variables.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: n = 3
Expected output: 3