Climbing Stairs
Problem Statement
You are climbing a staircase that takes n steps to reach the top. Each time you can climb either 1 or 2 steps. In how many distinct ways can you climb to the top?
Input
A single integer n, the number of steps to the top.
Output
An integer: the number of distinct ways to reach step n.
Constraints
- •
1 <= n <= 45
Examples
Example 1
n = 2
2Example 2
n = 3
3Learning Objectives
- Model a counting problem as a sum of smaller counting subproblems.
- Recognise the Fibonacci recurrence hiding inside a step-counting question.
- Reduce a 1D table to two rolling variables for O(1) space.
Intuition
Ask one focused question: how can you arrive at step n? Your very last move was either a single step from n - 1 or a double step from n - 2. There is no other way to land on n.
Those two groups never overlap, because they end with a different final move. So the number of ways to reach n is exactly the number of ways to reach n - 1 plus the number of ways to reach n - 2. That is the Fibonacci recurrence, and recognising it is the whole problem.
Common mistakes
- ×Trying to enumerate every path explicitly, which grows exponentially.
- ×Getting the base cases wrong: there is exactly one way to stand at step 0 and do nothing.
- ×Adding a factor for order; the two groups are already separated by their final move.
State Definition
Let dp[i] be the number of distinct ways to reach step i from the ground. The answer we want is dp[n].
State Transition
The final move onto step i came from step i - 1 as a 1-step or step i - 2 as a 2-step:
dp[i] = dp[i - 1] + dp[i - 2]
Base cases anchor the recurrence: dp[0] = 1 for the empty climb and dp[1] = 1 for a single 1-step.
Solutions
Solution: Bottom-up with two rolling variables
Because dp[i] depends only on the previous two values, you never need the whole array. Keep two variables for dp[i - 2] and dp[i - 1] and roll them forward.
Step-by-step
- Handle the tiny cases where n is 1 or 2 directly.
- Initialise twoStepsBack as the ways to reach step 1 and oneStepBack as the ways to reach step 2.
- Sweep from step 3 up to n, each time computing the current ways as the sum of the previous two.
- After the loop, oneStepBack holds dp[n].
O(n)
O(1)
A single pass with two integer variables.
Java implementation
Dry Run
Sample input
n = 5. Track the two rolling variables as the window slides from step 3 to step 5.
| step | twoStepsBack | oneStepBack | current |
|---|---|---|---|
| 3 | 1 | 2 | 3 |
| 4 | 2 | 3 | 5 |
| 5 | 3 | 5 | 8 |
The final value of oneStepBack is 8, so there are 8 distinct ways to climb 5 steps.
Complexity Analysis
The rolling-variable form runs in linear time and constant space, which is what an interviewer expects once you spot the Fibonacci structure.
Bottom-up with two rolling variables
O(n)
O(1)
A single pass with two integer variables.
Interview Tips
State up front that this is Fibonacci in disguise. Derive the recurrence from the last move, name the base cases, then mention you can drop the array to two variables. Interviewers often follow up by changing the allowed step sizes, which turns the two-term recurrence into a wider window.
Likely follow-ups
- What if you can climb 1, 2, or 3 steps at a time?
- What if each step has a cost and you want the minimum-cost climb?
- How would you count ways when some steps are broken and cannot be used?
Similar Problems
Key Takeaways
- Counting problems often decompose into a sum over the possible last moves.
- Climbing Stairs is the Fibonacci recurrence **dp[i] = dp[i - 1] + dp[i - 2]**.
- When **dp[i]** depends only on a fixed window, reduce the array to a few variables.