Interview preparation
Climbing Stairs
EasyDynamic ProgrammingRecursion
1Problem statement
You are climbing a staircase with n steps. Each time you can climb 1 or 2 steps. In how many distinct ways can you reach the top?
2Examples
Input: n = 2
Output: 2
Explanation: 1+1, 2
Input: n = 3
Output: 3
Explanation: 1+1+1, 1+2, 2+1
Input: n = 5
Output: 8
3Constraints
- 1 ≤ n ≤ 45
4Approaches
Approach 1
Brute Force: Plain recursion
ways(n) = ways(n−1) + ways(n−2) without caching — recomputes the same subproblems.
Time O(2ⁿ)Space O(n)
Approach 2
Better: Memoization / tabulation
Store ways(k) for every k in an array.
Time O(n)Space O(n)
Approach 3
Optimal: Two variables
Only the last two values are needed — keep them in two variables (Fibonacci).
Time O(n)Space O(1)
5Code (optimal approach)
Complete programs that print the example outputs — verified in JavaScript, Python, Java and Go.
6Complexity
Time
O(n)
Space
O(1)
7Visual walkthrough
- 1.ways(1) = 1, ways(2) = 2
- 2.ways(3) = 2 + 1 = 3
- 3.ways(4) = 3 + 2 = 5
- 4.ways(5) = 5 + 3 = 8