Module 23 · Dynamic Programming I: One-Dimensional State

222. Climbing Stairs

Foundation · Download this solution · All solutions and shared helpers

Problem

Count distinct ordered ways to climb exactly n steps using moves of one or two steps, for n>=0. Different move orders count separately. There is one way to climb zero steps: take no moves. Return an exact integer.

Examples

Example 1

climb_stairs(3)
=> 3

The three ordered move sequences are distinct.

Example 2

climb_stairs(0)
=> 1

The empty move sequence is one valid route.

Example 3

climb_stairs(2)
=> 2

Either two single steps or one double step reaches the top.

Reveal the worked solution and reasoning

Why this mechanism works

Classify routes by their final move. A one-step finish extends any route to n-1; a two-step finish extends any route to n-2. These classes are disjoint and exhaustive, so their counts add. Base counts are ways(0)=1 and ways(1)=1.

State and boundaries

Before computing step i>=2, previous=ways(i-2) and current=ways(i-1).

Protocol

Return one for n<=1.
Initialize the two base counts.
For steps 2 through n, advance to (current,previous+current).
Return current.

Visualization

n=3: [1,1,1], [1,2], [2,1]
last move 1: extend two routes to step 2
last move 2: extend one route to step 1

Python implementation

def climb_stairs(n):
    if n <= 1:
        return 1
    previous = current = 1
    for _ in range(2, n + 1):
        previous, current = current, previous + current
    return current

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

climb_stairs(3)

L2 climb_stairs: if n <= 1:
n=3

L4 climb_stairs: previous = current = 1
n=3; previous=1; current=1

L5 climb_stairs: for _ in range(2, n + 1):
n=3; previous=1; current=1; _=2

L6 climb_stairs: previous, current = current, previous + current
n=3; previous=1; current=2; _=2

L5 climb_stairs: for _ in range(2, n + 1):
n=3; previous=1; current=2; _=3

L6 climb_stairs: previous, current = current, previous + current
n=3; previous=2; current=3; _=3

Result: 3. The three ordered move sequences are distinct.

climb_stairs(0)

L2 climb_stairs: if n <= 1:
n=0

Result: 1. The empty move sequence is one valid route.

Why the solution is correct

Removing the final move gives a unique shorter route in exactly one of the two predecessor classes. Conversely, appending that move creates a valid route. The sum recurrence therefore counts every route once. Rolling updates preserve the last two complete answers until n is reached.

Time and space

O(n) additions and O(1) integer variables; exact counts grow to O(n) bits, so constant-variable storage is not constant bit storage.

Common mistakes

Using ways(0)=0 removes routes that begin with a two-step move. Counting unordered numbers of ones and twos ignores distinct move sequences.

Reasoning card

State: Before computing step i>=2, previous=ways(i-2) and current=ways(i-1).

Invariant: Rolling states are the complete answers for recent step counts.

Decision to rehearse: Ways to reach i come from i-1 and i-2.

Finish: Return current

Transfer exercise

Allow moves from a supplied positive step-size set and define the corresponding sum over predecessor states.