Climbing Stairs Problem: How Do You Solve It?
Learn how to solve the climbing stairs problem with dynamic programming, its Fibonacci recurrence, and how to answer it in interviews.
Expected Interview Answer
The climbing stairs problem is solved with dynamic programming by recognizing that the number of ways to reach step n equals the sum of the ways to reach step n-1 and step n-2, which is exactly the Fibonacci recurrence, solvable in O(n) time and O(1) space.
Since each move takes either one or two steps, the last move to reach step n was either a single step from n-1 or a double step from n-2, so ways(n) = ways(n-1) + ways(n-2). A naive recursive solution recomputes the same subproblems exponentially many times, so the fix is either top-down memoization or a bottom-up loop that tracks only the last two values. The base cases are ways(0) = 1 (one way to stand still) and ways(1) = 1 (one way to take a single step). This pattern of "current state depends on the previous two states" recurs across many DP problems, making climbing stairs a canonical first DP interview question.
- O(n) time with a simple bottom-up loop
- O(1) space by tracking only two rolling variables
- Introduces the overlapping-subproblems DP mindset
- Directly maps to the Fibonacci recurrence
AI Mentor Explanation
Counting ways to climb n stairs one or two at a time is like counting the number of distinct over-by-over sequences a bowler could use to bowl exactly n deliveries, where each "chunk" bowled is worth one or two balls toward the target. The number of sequences ending at delivery n is the sum of sequences ending at n-1 (then one more ball) plus sequences ending at n-2 (then a two-ball chunk). A scorer who recomputes every sequence from scratch for each delivery count wastes enormous effort recounting the same partial sequences. Instead, keeping a running tally of the previous two delivery-count totals lets the scorer build up to n instantly, which is the essence of bottom-up dynamic programming.
Step-by-Step Explanation
Step 1
Define the recurrence
ways(n) = ways(n-1) + ways(n-2), since the last move was either a 1-step or a 2-step.
Step 2
Set base cases
ways(0) = 1 and ways(1) = 1, representing standing still or a single required step.
Step 3
Iterate bottom-up
Loop from 2 to n, computing each value from the previous two, avoiding recomputation.
Step 4
Reduce to O(1) space
Keep only two rolling variables (prev, curr) instead of a full array, since only the last two values are ever needed.
What Interviewer Expects
- Derive the recurrence ways(n) = ways(n-1) + ways(n-2) from first principles
- Identify this as equivalent to the Fibonacci sequence
- Explain why naive recursion is exponential (overlapping subproblems)
- Optimize from O(n) space (array) to O(1) space (two variables)
Common Mistakes
- Writing naive exponential recursion without memoization and calling it done
- Getting the base cases wrong (e.g. ways(0) = 0 instead of 1)
- Not recognizing the Fibonacci connection, leading to a more complex solution than needed
- Forgetting the space optimization when explicitly asked for O(1) space
Best Answer (HR Friendly)
“The climbing stairs problem asks how many distinct ways you can reach the top of n stairs if you can take one or two steps at a time. I solve it by noticing the last step taken was either size one or size two, so the number of ways to reach step n is just the ways to reach step n-1 plus the ways to reach step n-2 — the same pattern as the Fibonacci sequence, computed in linear time.”
Code Example
def climb_stairs(n: int) -> int:
if n <= 1:
return 1
prev, curr = 1, 1
for _ in range(2, n + 1):
prev, curr = curr, prev + curr
return curr
# climb_stairs(5) -> 8Follow-up Questions
- How would you solve this if you could also take three steps at a time?
- How would you modify the solution to also return one valid sequence of steps?
- What is the time and space complexity of the naive recursive solution without memoization?
- How does this problem relate to counting tilings of a 2xN board with dominoes?
MCQ Practice
1. What recurrence solves the climbing stairs problem when steps of 1 or 2 are allowed?
The last move was either a 1-step from n-1 or a 2-step from n-2, so the totals add together.
2. What is the optimal space complexity for solving climbing stairs?
Only the previous two values are ever needed, so two rolling variables suffice, giving O(1) space.
3. Why is the naive recursive solution without memoization inefficient?
Without caching, each call branches into two more calls, recomputing identical subproblems repeatedly, giving exponential time.
Flash Cards
What is the recurrence for climbing stairs with 1 or 2 step moves? — ways(n) = ways(n-1) + ways(n-2), with ways(0) = ways(1) = 1.
What well-known sequence does climbing stairs match? — The Fibonacci sequence.
What is the optimal time complexity for climbing stairs? — O(n), using a single bottom-up pass.
How do you reduce climbing stairs to O(1) space? — Track only the previous two computed values instead of a full DP array.