Climbing Stairs

Problem

A staircase has n steps. Starting from the ground, each move climbs either 1 step or 2 steps. Count the number of distinct sequences of moves that land exactly on the top step.

Two sequences differ if the step size taken differs at any point.

Examples

• n = 2 → 2 — either 1 + 1 or 2.
• n = 3 → 3 — 1+1+1, 1+2, or 2+1.
• n = 5 → 8 — the count follows the Fibonacci sequence.

Constraints

• 1 <= n <= 45

The upper bound is small, so even an O(n) scan runs instantly; the problem tests whether you recognize the recurrence, not whether your code scales. Naive branching recursion is O(2^n) and already becomes slow near n = 45.

Think about it first

TL;DR

The answer is the Fibonacci number f(n) with f(1)=1, f(2)=2; compute it bottom-up with two rolling variables — O(n) time, O(1) space.

The recurrence

Let f(k) be the number of distinct ways to reach step k. The final move onto step k is either a 1-step from k-1 or a 2-step from k-2, and those path sets are disjoint, so:

f(k) = f(k-1) + f(k-2)
f(0) = 1        # one way to "stand at the ground": do nothing
f(1) = 1

Approach 1 — Brute-force recursion

Directly translate the recurrence. Each call branches into two.

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

The call tree branches on every node and revisits the same subproblems repeatedly. For n = 5:

graph TD
    A["ways(5)"] --> B["ways(4)"]
    A --> C["ways(3)"]
    B --> D["ways(3)"]
    B --> E["ways(2)"]
    C --> F["ways(2)"]
    C --> G["ways(1)"]
    D --> H["ways(2)"]
    D --> I["ways(1)"]

ways(3) is computed twice and ways(2) three times; the duplication grows exponentially with n.

Complexity: O(2^n) time (the call tree is itself a Fibonacci tree), O(n) stack space.

Why it fails the constraints: at n = 45 this makes on the order of 2·10^9 calls — seconds to minutes — because each subproblem ways(k) is recomputed exponentially many times.

Approach 2 — Top-down memoization

There are only n distinct subproblems, ways(0) … ways(n). Cache each one the first time it is computed, and every later request is O(1).

from functools import cache

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

Walkthrough (n = 5): ways(5) needs ways(4)+ways(3). ways(4) computes ways(3)+ways(2); when ways(5) later asks for ways(3) it is already cached. Filled values are ways(2)=2, ways(3)=3, ways(4)=5, ways(5)=8 → 8.

Complexity: O(n) time (each ways(k) body runs once), O(n) space for cache + stack.

Approach 3 — Bottom-up tabulation

Compute the subproblems in increasing order of k, so every dependency is ready before it is needed. No recursion, no cache lookups.

def climbStairs(n: int) -> int:
    dp = [0] * (n + 1)
    dp[0] = dp[1] = 1
    for k in range(2, n + 1):
        dp[k] = dp[k - 1] + dp[k - 2]
    return dp[n]

Complexity: O(n) time, O(n) space for the table.

Approach 4 — Space-optimized (rolling variables)

dp[k] only ever reads dp[k-1] and dp[k-2]. Keep just those two numbers and slide them forward; the full array is unnecessary.

def climbStairs(n: int) -> int:
    prev, curr = 1, 1                 # f(0), f(1)
    for _ in range(2, n + 1):
        prev, curr = curr, prev + curr
    return curr

Walkthrough (n = 5): start (prev, curr) = (1, 1). Iterations: (1,2) → (2,3) → (3,5) → (5,8). Return curr = 8.

Complexity: O(n) time, O(1) space — the optimal version.

Common pitfalls

• Base cases off by one. f(1) is 1, not 2. A common slip is seeding f(2) = 3; keep f(0) = f(1) = 1 and let the loop derive the rest.
• Returning curr when n = 1. With the two-variable version above, n = 1 skips the loop and returns the initial curr = 1, which is correct — but only because both variables were seeded to 1. Double-check the tiny cases.
• Using plain recursion under a tight limit. Correct but exponential; always add memoization or go bottom-up.

Pattern takeaway

This is the canonical 1-D DP: define f(k) over a single index, split on the last decision (which step size finished the path), and you get a linear recurrence. Whenever the answer at n decomposes into a fixed set of smaller indices, cache those subproblems. If each state reads only a constant-width window behind it, collapse the table to a few rolling variables for O(1) space.