How to Explain Climbing Stairs in a Coding Interview (Step-by-Step)
Climbing Stairs is the classic entry point into dynamic programming — and the problem most interviewers use to test whether you recognise the DP pattern. The brute force is exponential. The key is spotting that this is just Fibonacci in disguise.
In this post, you’ll learn exactly how to walk an interviewer through this problem: why naive recursion explodes, how memoisation fixes it, and how to arrive at the elegant O(n) time O(1) space bottom-up solution.
Problem Statement
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?
Examples
Output: 2
Explanation: Two ways — (1+1) or (2)
Output: 3
Explanation: Three ways — (1+1+1), (1+2), (2+1)
Output: 8
Constraints
1 <= n <= 45
What Is the Problem?
“I need to count the number of distinct ways to climb n stairs where each step can be 1 or 2 stairs at a time. Order matters — taking 1 then 2 is different from taking 2 then 1.”
Step 1: Walk Through All Three Approaches
Recursively branch at every step — try taking 1 or 2
Time: O(2ⁿ) — exponential branching
Space: O(n) call stack
Recomputes same subproblems repeatedly
Cache results of subproblems in a dictionary
Time: O(n)
Space: O(n) memo + O(n) stack
Good — eliminates redundant computation
Build up from base cases using two variables
Time: O(n)
Space: O(1)
No recursion, no extra array — pure Fibonacci
The Key Insight — This Is Fibonacci
To reach step n, you must have come from either step n−1 (took 1 step) or step n−2 (took 2 steps). So the number of ways to reach step n equals the number of ways to reach step n−1 plus the number of ways to reach step n−2.
That’s the Fibonacci sequence: f(n) = f(n−1) + f(n−2). Climbing Stairs with base cases f(1)=1, f(2)=2 produces the Fibonacci numbers offset by one position.
“The moment I recognise this is Fibonacci, I know I only need two variables — I don’t need a full array or recursion. I just slide a window of two values forward n times.”
The Recurrence Relation
Why these base cases?
“With 1 step, there’s only 1 way: take 1 step. With 2 steps, there are 2 ways: (1+1) or (2). Every subsequent value is just the sum of the previous two.”
Step 3: Talk Through the Code
Approach 1 — Memoisation (mention first)
class Solution:
def climbStairs(self, n: int) -> int:
memo = {} # Cache to avoid recomputing subproblems
def dp(i):
if i <= 1: return 1 # Base case: 1 way to be at step 0 or 1
if i in memo: return memo[i]
memo[i] = dp(i-1) + dp(i-2) # Recurrence
return memo[i]
return dp(n)Approach 2 — Bottom-Up O(1) Space (optimal, lead with this)
class Solution:
def climbStairs(self, n: int) -> int:
if n <= 2:
return n # Base cases: n=1→1, n=2→2
prev2 = 1 # ways(1) — two steps back
prev1 = 2 # ways(2) — one step back
for i in range(3, n + 1):
curr = prev1 + prev2 # ways(i) = ways(i-1) + ways(i-2)
prev2 = prev1 # Slide window forward
prev1 = curr
return prev1 # prev1 now holds ways(n)Point out that we only ever need the last two values — so two variables replace the entire DP array. This is the Fibonacci rolling variable trick.
Visual Walkthrough
Tracing the bottom-up solution for n = 6:
| Step i | prev2 (i−2) | prev1 (i−1) | curr = prev1 + prev2 | Meaning |
|---|---|---|---|---|
| 1 | — | 1 | — | Base case: 1 way |
| 2 | 1 | 2 | — | Base case: 2 ways |
| 3 | 1 | 2 | 3 | 1+2+1+1+1, 2+1, 1+2 |
| 4 | 2 | 3 | 5 | 5 distinct ways |
| 5 | 3 | 5 | 8 | 8 distinct ways |
| 6 | 5 | 8 | 13 ★ | Answer for n=6 |
Notice the sequence: 1, 2, 3, 5, 8, 13… — that's the Fibonacci sequence shifted by one position. Pointing this out in an interview shows pattern recognition beyond just solving the problem.
Step 4: Highlight Edge Cases
"Only one way to climb 1 stair — take 1 step. The base case handles this directly: return 1. No loop runs."
"Two ways: (1+1) or (2). The base case returns 2. Without this check, the loop would start at 3 and never compute for n=2 correctly with two initialised variables."
"The constraint caps at n=45 so no overflow in Python. The answer for n=45 is 1,836,311,903 — fits comfortably in a 32-bit integer. Python handles big integers natively anyway."
"The closed-form Binet's formula exists but involves floating point — unreliable for large n due to precision errors. The iterative DP approach is exact and O(n). Mention this if the interviewer asks about a mathematical shortcut."
Step 5: State Time and Space Complexity
| Approach | Time | Space |
|---|---|---|
| Brute Force Recursion | O(2ⁿ) | O(n) stack |
| Memoisation | O(n) | O(n) memo + stack |
| Bottom-Up DP ✓ | O(n) | O(1) |
"The bottom-up approach loops once from 3 to n — O(n) time. We only store two variables regardless of n — O(1) space. It's strictly better than memoisation in space because we eliminate both the hash map and the recursion stack."
Interview Checklist for Climbing Stairs
- Restate — "count distinct ways to reach step n taking 1 or 2 steps at a time"
- Mention brute force recursion O(2ⁿ) and why it's slow — redundant subproblems
- Spot the Fibonacci pattern —
ways(n) = ways(n−1) + ways(n−2) - State base cases clearly —
ways(1) = 1,ways(2) = 2 - Mention memoisation as the top-down DP fix
- Arrive at bottom-up with two variables — no array, no recursion
- Handle n=1 and n=2 base cases explicitly
- State O(n) time and O(1) space
- Optionally mention Binet's formula exists but has floating-point issues
- Ask before coding, don't just dive in
Related Problems to Practice
If you can solve Climbing Stairs cleanly, try these next: