Climbing Stairs

Easy

Dynamic Programming

Ways to reach step n = ways to reach n−1 plus n−2.

Rolling DP Trace

prev2 = f(0) = 1 and prev1 = f(1) = 1: one way to stand at the bottom, and one way to reach step 1.

StopDP tableExport

Steps

CH1 prev2
CH2 prev1

Problem

You are climbing a staircase with n steps. From any step, you may move up either one step or two steps. Return the total number of distinct sequences of moves that land exactly on the top.

Examples

Input: n = 4

Output: 5

The valid move sequences are 1+1+1+1, 1+1+2, 1+2+1, 2+1+1, and 2+2.

Input: n = 5

Output: 8

There are 8 sequences of one-step and two-step moves whose totals equal 5.

The Goal

Count the different orders of 1-step and 2-step moves that land exactly on step n. Order matters: 1+2 and 2+1 are two routes.

Every route to step n ends with a 1-step move from n - 1 or a 2-step move from n - 2. No route ends both ways, so you can add the two counts.

Count ordered move sequences

For n = 4, the five routes are 1111, 112, 121, 211 and 22.

The Fibonacci Recurrence

Let f(k) be the number of routes to step k. Splitting routes by their last move gives:

f(k) = f(k - 1) + f(k - 2)

The bases are f(0) = 1, the empty route, and f(1) = 1. With f(0) = 0, the route that's a single 2-step move wouldn't count.

So f(2) = 1 + 1 = 2, and f(3) = 2 + 1 = 3.

f(k) = f(k - 1) + f(k - 2).

f(5) = 5 + 3 = 8.

Bottom-Up with Two Variables

Each value needs only the two before it, so you don't need an array. Keep prev2 = f(k - 2) and prev1 = f(k - 1), and shift them forward each step.

python

def climb_stairs(n):
    prev2, prev1 = 1, 1
    for _ in range(2, n + 1):
        prev2, prev1 = prev1, prev1 + prev2
    return prev1

Assign both at once, so the old prev1 isn't lost. For n = 1 the loop never runs, and prev1 = 1 is already the answer.

Walkthrough

Run it with n = 5. The pair starts at 1, 1.

Each step adds the pair and shifts it along: f(2) = 2, f(3) = 3, f(4) = 5, f(5) = 8. The stage strikes out each value once the pair has moved past it, because nothing reads it again.

The answer is prev1 = 8.

Checkpoint · predict the next step

Step 3 of 6 on the stage: f(3) = prev1 + prev2 = 2 + 1 = 3. Shift the pair: prev2 = f(2), prev1 = f(3).

f = [1, 1, 2, 3, ·, ·]

What does step 4 show?f = [1, 1, 2, 3, 5, 8]f = [1, 1, 2, 3, 5, ·]f = [1, 1, 2, 3, ·, ·]f = [1, 1, 2, ·, ·, ·]

Step through it on the stage

Pitfalls

Plain recursion recomputes the same values. f(5) asks for f(4) and f(3), and f(4) asks for f(3) again. That's O(2^n).
Memoization or a bottom-up loop computes each value once.
Test n = 1, where the loop never runs.

Why is plain recursion slow for large n?

Complexity

The loop does one addition per step, n - 1 times: O(n) time. You keep two numbers whatever n is, so extra space is O(1).

Whenever a value depends on a fixed number of earlier values, a rolling pair like this can replace the whole table.

Rolling DP

Time

O(n)

Space

O(1)

Where the time goes

Start the pairTwo base values.O(1)
Compute f(2) through f(n)One addition and shift each.dominantO(n)
Rolling stateTwo values kept.O(1)

How it grows

Roughly what that costs

n	10	100	1,000	10,000
O(n)	10	100	1K	10K

Each value is computed once, in constant memory.

In short

Each step is reached from one or two below it, so the count is the Fibonacci recurrence f(n) = f(n−1) + f(n−2). Compute bottom-up with two rolling variables instead of a full array for O(1) space.

TimeO(n)SpaceO(1)

Common mistake

Plain recursion without memoization, which recomputes the same subproblems exponentially.

NextHouse Robber →At each house choose the better of robbing it (plus two back) or skipping it.

House RobberMedium Coin ChangeMedium