You’re in a coding interview. The interviewer says: “You’re climbing a staircase with n steps. You can take 1 or 2 steps at a time. How many distinct ways can you reach the top?” You’ve seen Climbing Stairs before. You know it’s Fibonacci under the hood. But now you need to walk through the full progression from naive recursion to O(1) space, explain each optimization step out loud, and handle the follow-up about taking 3 steps at a time. That’s a very different challenge.

This walkthrough covers how that conversation unfolds: the clarifying questions worth asking, the four-step optimization journey interviewers want to see, and the common traps that catch candidates who think “easy” means “safe.”

---

The Problem

You are climbing a staircase with n steps. Each time you can either climb 1 step or 2 steps. Return the number of distinct ways you can reach the top. (LeetCode #70)

Example

Input

n = 5

Output

8

For n = 3, there are 3 ways: {1,1,1}, {1,2}, {2,1}. For n = 5, there are 8 ways. The pattern here is not coincidental: the answers follow the Fibonacci sequence (1, 1, 2, 3, 5, 8, 13…), a connection worth recognizing and mentioning in your interview.

Already comfortable with the solution? Practice it in a mock interview →

---

What Interviewers Are Actually Testing

The Climbing Stairs interview is a deliberate DP entry point. Interviewers use it to see how you decompose a problem into smaller pieces and whether you naturally think in terms of subproblems and state transitions. A candidate who jumps straight to the Fibonacci observation without working through the reasoning misses the point: the reasoning is the interview.

Skill	What Interviewers Observe
Recursive decomposition	Can you express f(n) in terms of smaller subproblems?
Recurrence recognition	Do you identify that ways(n) = ways(n-1) + ways(n-2)?
DP optimization instinct	Do you move from recursion → memoization → bottom-up naturally?
Space optimization	Can you reduce O(n) space to O(1) using two variables?
Base case precision	Do you correctly define ways(1) = 1 and ways(2) = 2?
Fibonacci connection	Do you recognize and name the underlying mathematical pattern?

---

Step 1: Clarifying Questions

Even for a short, well-defined problem, asking smart questions signals that you think before you code. Here are the most valuable ones for Climbing Stairs:

1. Can I only take 1 or 2 steps at a time, or are larger jumps allowed? The problem constrains you to 1 or 2 steps. Confirming this prevents you from designing a more general solution. It also shows you read constraints carefully.

2. What is the minimum value of n? Can n be 0 or negative? LeetCode constrains n >= 1, but asking this forces you to think about base cases. If n = 0 were valid, is the answer 1 (one way to “stay put”) or 0? Clarifying avoids ambiguous base case logic.

3. Are we counting ordered sequences or unordered combinations? {1, 2} and {2, 1} are considered different paths. Confirming this matters. It’s a subtle distinction that demonstrates you’re thinking about the problem space carefully.

4. Is there a constraint on n that hints at the expected time complexity? If n can reach 45 (as in the LeetCode constraints), an exponential solution is too slow. Knowing the range lets you justify why O(n) is the target.

---

Step 2: A First (Non-Optimal) Idea

The most natural first approach is pure recursion: to reach step n, you either came from step n-1 (taking one step) or step n-2 (taking two steps). So the total number of ways to reach n is the sum of ways to reach n-1 and n-2.

def climbStairs(n):
    if n <= 1:
        return 1
    return climbStairs(n - 1) + climbStairs(n - 2)

Approach	Time	Space
Naive recursion	O(2ⁿ)	O(n) call stack

This is beautifully simple and completely impractical. The time complexity is O(2ⁿ) because every call branches into two more calls, and the same subproblems are recomputed over and over. For n = 45, this means billions of redundant computations.

Draw the recursion tree if your interviewer asks you to. climbStairs(5) calls climbStairs(4) and climbStairs(3). climbStairs(4) calls climbStairs(3) again. climbStairs(3) is being solved multiple times, and that’s the signal that memoization can help.

Always present this first: “The recursive structure is clear, but we’re recomputing subproblems. That’s exactly the condition for dynamic programming.”

---

Step 3: The Key Insight

Every subproblem is solved more than once in the naive recursion, and every subproblem’s answer only depends on the two before it. The recurrence is ways(n) = ways(n-1) + ways(n-2), identical in structure to the Fibonacci sequence.

Once you see that, three progressively better implementations follow naturally:

Memoization (top-down DP): Cache the result of each ways(k) so you never compute it twice. Time drops to O(n), space is O(n) for the cache plus O(n) call stack.

Bottom-up DP (tabulation): Build a table from ways(1) up to ways(n) iteratively. Same O(n) time, O(n) space, but no recursion overhead.

Space-optimized (two variables): Since ways(n) only depends on the previous two values, you don’t need the full table. Just two variables that you slide forward. O(n) time, O(1) space.

The interviewer will likely ask you to reach this final optimization. Knowing the full progression and being able to explain each step is what makes a Climbing Stairs explanation genuinely impressive.

---

Step 4: Optimal Strategy

Here’s the bottom-up, space-optimized algorithm step by step:

1. Handle the base case: if n == 1, return 1.
2. Initialize two variables: prev2 = 1 (ways to reach step 1) and prev1 = 2 (ways to reach step 2).
3. If n == 2, return prev1 directly.
4. Iterate from step 3 up to step n (inclusive).
5. At each step, compute current = prev1 + prev2, the number of ways to reach the current step.
6. Slide the window forward: set prev2 = prev1, then prev1 = current.
7. After the loop, return prev1, which now holds the answer for step n.

The key to getting this right without bugs: be explicit about what prev1 and prev2 represent at each point in the loop, and trace through n = 4 or n = 5 mentally before declaring it done.

---

Python Implementation

def climbStairs(n: int) -> int:
    # Base cases: only one way to climb 1 step, two ways to climb 2 steps
    if n == 1:
        return 1
    if n == 2:
        return 2

    # prev2 = ways(i-2), prev1 = ways(i-1)
    prev2, prev1 = 1, 2

    for i in range(3, n + 1):
        # Ways to reach step i = ways from step i-1 + ways from step i-2
        current = prev1 + prev2

        # Slide the window forward
        prev2 = prev1
        prev1 = current

    return prev1  # Now holds ways(n)

Style notes worth calling out in an interview:

• Handling n == 1 and n == 2 explicitly as base cases keeps the loop logic clean and avoids subtle off-by-one errors.
• Variable names prev1 and prev2 communicate their roles clearly. They represent ways(i-1) and ways(i-2) relative to the current iteration.
• The sliding window pattern (prev2 = prev1, prev1 = current) is a reusable idiom across many Fibonacci-style DP problems, worth naming explicitly.

For completeness, here’s also the memoized version, which some interviewers prefer to see first as a stepping stone:

from functools import lru_cache

def climbStairs(n: int) -> int:
    @lru_cache(maxsize=None)
    def ways(k):
        if k <= 1:
            return 1
        if k == 2:
            return 2
        return ways(k - 1) + ways(k - 2)

    return ways(n)

---

Time & Space Complexity

Operation	Complexity
Time (naive recursion)	O(2ⁿ)
Time (memoized / bottom-up)	O(n)
Space (memoized)	O(n)
Space (bottom-up optimized)	O(1)

Time: In the optimized solution, we make a single pass from step 3 to step n, exactly n - 2 iterations, so O(n) overall.

Space: We store only two variables at any point, regardless of n. This is the key win over the memoization approach, and worth highlighting: “I’ve reduced space from O(n) to O(1) by observing that the recurrence only looks back two steps.”

---

Common Interview Mistakes

1. Returning the wrong base case for n = 1. Some candidates write if n == 0: return 1 and if n == 1: return 1, which works but requires careful reasoning. Being explicit with n == 1 → 1 and n == 2 → 2 is cleaner and less error-prone.

2. Off-by-one in the loop range. Using range(2, n) instead of range(3, n + 1) shifts the entire iteration, producing wrong results. Always trace through a small example (n = 4) to verify your loop bounds.

3. Presenting only the recursive solution without optimizing. The naive recursion is the starting point, not the answer. Stopping there signals you don’t know DP. Always drive toward memoization and then bottom-up.

4. Not naming the Fibonacci connection. Recognizing that the answer is the (n+1)th Fibonacci number is a signal of mathematical maturity. Not mentioning it when you clearly see it is a missed opportunity.

5. Confusing prev1 and prev2 after the slide. The update order matters: you must set prev2 = prev1 before setting prev1 = current. Doing it in the wrong order overwrites a value you still need. Trace through once to confirm.

6. Not explaining the recurrence before coding. Candidates who write the loop without first saying “to reach step n, I either came from n-1 or n-2, so ways(n) = ways(n-1) + ways(n-2)” leave the interviewer guessing whether they understand the problem or just memorized the solution.

7. Ignoring the space optimization. Getting to a working O(n) space bottom-up DP is good. Getting to O(1) by noting the recurrence only needs two prior values is great. Interviewers often prompt for this; have the answer ready.

---

What a Strong Candidate Sounds Like

“My first instinct is to think recursively: to reach step n, I either took one step from n-1 or two steps from n-2. So the number of ways to reach n is just ways(n-1) plus ways(n-2), a classic recurrence.

The naive recursion is O(2ⁿ) because we recompute the same subproblems repeatedly. That’s the cue for dynamic programming. I can memoize to get O(n) time and space, or go bottom-up and build from the base cases up.

Since the recurrence only looks back two steps, I don’t need a full table. Just two variables. I’ll slide them forward each iteration to get O(n) time and O(1) space. This is essentially computing Fibonacci numbers, which is a nice property worth noting.

Let me code that up and trace through n = 5 to verify.”

---

Example Interview Dialogue

Interviewer: How many ways can you climb n stairs if you can take 1 or 2 steps at a time?

Candidate: Before I start, can I confirm the steps are ordered? Meaning {1, 2} and {2, 1} count as different paths?

Interviewer: Yes, order matters.

Candidate: Good. My first observation: to reach step n, I either arrived from step n-1 or step n-2. So ways(n) = ways(n-1) + ways(n-2). That’s a Fibonacci recurrence. Naively, I could recurse, but that’s O(2ⁿ) because I’d recompute the same steps repeatedly.

Interviewer: How would you fix that?

Candidate: Memoize the recursion to get O(n) time and space. But I can go further: since I only ever look back two values, I can replace the full memo table with two variables and slide them forward. That gives O(n) time and O(1) space.

Interviewer: What if you could also take 3 steps at a time?

Candidate: Then the recurrence becomes ways(n) = ways(n-1) + ways(n-2) + ways(n-3). I’d need three variables instead of two, prev3, prev2, and prev1, and add a third base case for n == 3. The structure is the same, just extended by one term.

---

Related Problems to Practice

Climbing Stairs is the seed of an entire DP pattern family. These problems share the same “build the answer from smaller subproblems” structure:

• House Robber (LeetCode #198). Same 1D DP with a constraint on which elements you can pick, a direct extension of Climbing Stairs logic.
• Coin Change (LeetCode #322). Generalized step-climbing where “step sizes” are coin denominations. Introduces unbounded choices.
• Longest Increasing Subsequence (LeetCode #300). 1D DP where the recurrence depends on earlier states. Builds on the same bottom-up pattern.
• Fibonacci Number (LeetCode #509). The mathematical foundation of Climbing Stairs, worth solving explicitly to cement the base pattern.
• Min Cost Climbing Stairs (LeetCode #746). Climbing Stairs with a cost at each step. Adds a minimization dimension to the same recurrence.

If an interviewer gives you Climbing Stairs as a warm-up, House Robber is the most natural follow-up. Being ready for that pivot is itself a strong signal.

---

Practice This in a Mock Interview

Reading through this Climbing Stairs explanation gives you the intellectual foundation: the recurrence, the optimization steps, and the Fibonacci connection. But understanding it and performing it under interview conditions are genuinely different skills.

When someone is watching a clock and asking follow-up questions, candidates who “knew” the solution find themselves second-guessing base cases, fumbling variable names, and losing track of the recurrence. The only way to build the reflexes that make DP feel natural is to practice solving it out loud, repeatedly, with feedback.

Start a mock interview for Climbing Stairs on Intervu.

Further reading:

• How to Prepare for a Coding Interview in 2026, the complete roadmap and study plans
• Why LeetCode alone isn’t enough, and what to practice instead
• Practice any LeetCode problem as a live mock interview
• The Grind 75 Pathway, a structured study plan with AI practice links
• Browse all walkthroughs on GitHub, condensed solutions with code