16 / 75
Easy
Climbing Stairs
#16dynamic-programmingmathmemoization
Count distinct ways to climb n stairs when you can take 1 or 2 steps at a time.
Example:
Input:
3Output:
3 (explanations: 1+1+1, 1+2, 2+1)Common Mistakes:
- Using recursion without memoization (exponential time)
- Not recognizing Fibonacci pattern
- Using array when two variables suffice
Notes:
This is the Fibonacci sequence! At step n, you either came from n-1 (1 step) or n-2 (2 steps). Time: O(n), Space: O(1). Base: f(1)=1, f(2)=2.
💻
Java Solution Hidden
Enable “Show Full Solution” to view the code
Count distinct ways to climb n stairs when you can take 1 or 2 steps at a time.
Example:
Input:
3Output:
3 (explanations: 1+1+1, 1+2, 2+1)Common Mistakes:
- Using recursion without memoization (exponential time)
- Not recognizing Fibonacci pattern
- Using array when two variables suffice
Notes:
This is the Fibonacci sequence! At step n, you either came from n-1 (1 step) or n-2 (2 steps). Time: O(n), Space: O(1). Base: f(1)=1, f(2)=2.
16/75
Climbing Stairs