Climbing stairs
viaLeetCode
Problem Count the distinct ways to climb a staircase of n steps if each move climbs 1 or 2 steps.
Input / Output
- Input: integer n.
- Output: number of distinct step sequences reaching step n.
Constraints
- 1 <= n <= 45 (fits in int; answer is Fibonacci-sized).
Example
- n = 3 → 3 ([1,1,1], [1,2], [2,1])
- n = 4 → 5
Expected approach
- DP: ways(n) = ways(n-1) + ways(n-2) with ways(1)=1, ways(2)=2 — the Fibonacci recurrence. Two rolling variables give O(n) time, O(1) space. Mention memoization vs bottom-up, and the follow-up-friendly generalizations (step sizes {1..k}, or matrix exponentiation / fast doubling for O(log n)).
asked …