Coding interview problems › Dynamic Programming

🪙 Dynamic Programming Easy

Climbing Stairs

Climbing Stairs explained: why the number of ways follows Fibonacci, from naive recursion to memoization to O(1)-space DP, with tested Python and a live visual.

Also searched as: climbing stairs dp · count ways to climb n stairs with 1 or 2 steps · fibonacci staircase problem

🪆

Try it live Free

Recursion & the Call Stack

Step through the recursive call and watch the call stack grow and unwind, then switch on memoization and watch the blow-up of repeated calls disappear.

Also useful: Coin Change (DP)

Open the playground →

The problem

You are at the bottom of a staircase with n steps. Each move climbs either 1 or 2 steps. Count how many different sequences of moves take you exactly to the top.

Inputn = 3
Output3

1+1+1, 1+2, 2+1

Inputn = 5
Output8

The key insight

Think about the last move. To stand on step n you arrived either from step n-1 (a 1-step) or from step n-2 (a 2-step). So ways(n) = ways(n-1) + ways(n-2), the Fibonacci recurrence. Plain recursion recomputes the same steps again and again; remembering each answer once makes it linear.

Brute force first: Direct recursion ways(n-1) + ways(n-2) without memory makes about 2n calls, because every sub-answer is recomputed many times.

Step-by-step approach

  1. Define ways(i) as the number of ways to reach step i.
  2. Base cases: ways(0) = 1 (stand still) and ways(1) = 1.
  3. For each i from 2 to n, ways(i) = ways(i-1) + ways(i-2).
  4. You only ever need the last two values, so keep two variables instead of a whole array.
  5. Return the value for step n.

Python solution

PYTHON 3tested
def climb_stairs(n):
    a, b = 1, 1          # ways(i-2), ways(i-1) starting at ways(0), ways(1)
    for _ in range(n - 1):
        a, b = b, a + b
    return b if n >= 1 else 1

Complexity

TimeO(n)
SpaceO(1)

One loop iteration per step, each doing constant work. Only the two previous answers are stored.

Common mistakes

Frequently asked questions

What is the time and space complexity of Climbing Stairs?

The bottom-up version runs in O(n) time and O(1) extra space. A memoized recursion is also O(n) time but uses O(n) space for the cache and the call stack.

Why is Climbing Stairs the same as Fibonacci?

Every path to step n ends with either a 1-step from n-1 or a 2-step from n-2, so the count is the sum of the two previous counts, which is exactly the Fibonacci rule.

What if you can climb 1, 2 or 3 steps?

Add one more term: ways(n) = ways(n-1) + ways(n-2) + ways(n-3). In general, with a set of allowed step sizes, sum ways(n - s) over every allowed s, which is the coin change counting idea with order mattering.

Is there a faster than O(n) solution?

Yes, Fibonacci numbers can be computed in O(log n) with fast matrix exponentiation, but interviewers almost always expect the O(n) DP.

Preparing for placements?

Take the 2-minute readiness check to find your weak patterns, then follow the placement path from DSA core to system design.

📋 2-minute readiness check The full placement path

All coding interview problems More Dynamic Programming Coin Change (DP) lab Placement prep guides

Problem statements on this site are written in our own words. Problem names are the common names used across interview-prep communities; BitBootcamp is an independent learning platform and is not affiliated with LeetCode or any company that asks these questions.