Back to All Questions
Climbing Stairs
Google
Dynamic Programming
Math
You are climbing a staircase. It takes n steps to reach the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
Example:
Input: n = 4 Output: 5 Explanation: [1,1,1,1], [1,1,2], [1,2,1], [2,1,1], [2,2]
Solution Walkthrough
The number of ways to reach step n is the sum of the ways to reach step n-1 (then take one final 1-step) and step n-2 (then take one final 2-step). That recurrence is exactly the Fibonacci sequence.
- Handle the base cases directly: there's 1 way to reach step 1, and 2 ways to reach step 2.
- Instead of recursing naively (which recomputes the same subproblems exponentially many times), iterate from step 3 up to
n, tracking only the previous two results. - At each step, the current count is the sum of the previous two counts. Shift the "previous two" window forward by one.
- After the loop, the current count is the answer for
n.
Because we only keep two rolling variables instead of a full DP array, this runs in O(n) time and O(1) space — a bottom-up rewrite of what would otherwise be an O(2ⁿ) naive recursive solution.
1 2 3 4 5 6 7 8 9 10 11 12 13 14