Climbing Stairs
Count the ways to climb n steps taking one or two at a time. The smallest example of dynamic programming, and a direct route to the Fibonacci recurrence. Solve it below in Python or JavaScript, then read the walkthrough.
Problem
A staircase has n steps. On each move you climb either 1 step or 2 steps.
Return the number of distinct sequences of moves that take you from the bottom to exactly the top step. Two sequences are different if they differ in at least one move, so 1 then 2 is not the same as 2 then 1.
Example 1
- Input
- n = 4
- Output
- 5
The sequences are 1+1+1+1, 1+1+2, 1+2+1, 2+1+1 and 2+2.
Example 2
- Input
- n = 6
- Output
- 13
Example 3
- Input
- n = 1
- Output
- 1
The only option is a single 1-step move.
Constraints
- 1 ≤ n ≤ 45
- The answer fits in a 32-bit signed integer.
Practice
Runs 10 tests in your browser. Python loads on the first run (about 6 MB, then cached). Press ⌘/Ctrl + Enter to run.
Get asked Climbing Stairs in a real interview?
Interview Solver gives you a working solution live, during your actual coding interview. Invisible to screensharing.
How to solve Climbing Stairs
Pattern: 1D dynamic programming
Think about the last move. Any way of reaching step n ends with either a 1-step move from step n - 1 or a 2-step move from step n - 2. Those two groups don't overlap and together cover everything, so:
ways(n) = ways(n - 1) + ways(n - 2), with ways(1) = 1 and ways(2) = 2.
That's the Fibonacci recurrence, shifted by one. The pattern to spot is a counting question where the answer for n is built from answers to a few smaller sizes. Plain recursion recomputes the same sizes over and over, so either cache them or build up from the bottom. Since each value only needs the previous two, two variables are enough.
Approach 1: Plain recursion
Return climb(n - 1) + climb(n - 2) with base cases for 1 and 2. It is the recurrence written directly, but the call tree branches twice at every level and recomputes the same values exponentially many times. n = 45 takes over a billion calls.
Time O(2ⁿ) · Space O(n) call stack
Approach 2: Memoized recursion or a DP table
Store each ways(i) the first time you compute it, either in a cache on the recursive function or in an array filled from i = 1 upward. Every value is computed once.
Time O(n) · Space O(n)
Approach 3: Bottom-up with two variables
Only the previous two answers matter, so keep just those. Start with prev = 1 (ways to reach step 1) and curr = 2 (step 2), then for each step from 3 to n, set prev, curr = curr, prev + curr. Return prev when n = 1, otherwise curr.
Time O(n) · Space O(1)
| Approach | Time | Space |
|---|---|---|
| Plain recursion | O(2ⁿ) | O(n) call stack |
| Memoized recursion or a DP table | O(n) | O(n) |
| Bottom-up with two variables | O(n) | O(1) |
Solution code
Try the practice editor first. Both solutions pass every test above.
Climbing Stairs solution in Python
def climb_stairs(n: int) -> int:
if n == 1:
return 1
prev, curr = 1, 2 # ways to reach steps 1 and 2
for _ in range(3, n + 1):
prev, curr = curr, prev + curr
return currClimbing Stairs solution in JavaScript
function climbStairs(n) {
if (n === 1) return 1;
let prev = 1; // ways to reach step 1
let curr = 2; // ways to reach step 2
for (let i = 3; i <= n; i++) {
[prev, curr] = [curr, prev + curr];
}
return curr;
}Common mistakes
- Off-by-one base cases. With ways(0) = 1 and ways(1) = 1 the recurrence also works, but mixing the two conventions gives answers shifted by one position.
- Writing the naive recursion and assuming it is fast enough. It times out well before n = 45.
- Counting combinations instead of sequences. 1+2 and 2+1 are different ways here.
- Forgetting the n = 1 case when the loop starts at step 3.
What interviewers look for
The interviewer mostly wants to hear the reasoning behind the recurrence: "every path ends with a 1-step or a 2-step, so the count is the sum of the two smaller counts." Say that before you write any code. Then show the progression from recursion, to memoization, to two variables, and give the cost of each.
Check your base cases by hand against n = 3 (three ways: 1+1+1, 1+2, 2+1). If you mention the closed-form or matrix-power solution, keep it short unless they ask.
Follow-up questions
What if you can climb 1, 2, or 3 steps at a time, or any set of step sizes?
Generalize the recurrence to ways(n) = sum of ways(n - s) for each allowed step size s, with ways(0) = 1 and ways(negative) = 0. It runs in O(n · number of step sizes) with a window of the last max(s) values.
Can you do better than O(n)?
Yes. The recurrence is a linear map on the pair (ways(n), ways(n - 1)), so raising the 2×2 matrix [[1, 1], [1, 0]] to the n-th power by repeated squaring gives the answer in O(log n) multiplications.
What if some steps are broken and can’t be stepped on?
Set ways(i) = 0 for every broken step and use the same recurrence for the rest. Paths through a broken step automatically contribute nothing.
Companies that ask Climbing Stairs
Climbing Stairs is tagged by 130 companies in our interview dataset. The score shows how often it comes up at each company.
- Raytheon100%
- Project44100%
- Hpe100%
- Atos96%
- Philips96%
- General Dynamics Mission Systems94%
- Skillz92%
- Metabase92%
- Daimler91%
- Rakuten88%
- Highradius87%
- Accenture86%
- Grammarly84.4%
- Adobe84.3%
- Genentech83%
- Surveymonkey83%
- Hsbc81.3%
- Zoho80.7%
- Bombbomb80%
- Synchrony79%
- Pegasystems78%
- Cummins77%
- Eightfold AI77%
- Chargebee77%
and 106 more.
Practice next
Get live help in the real interview
Working solutions in real time during your actual interview. Invisible to screensharing.
Start Free TrialNo credit card required