Data Structures
powered by pagefind esc close · ↑↓ navigate · ↵ open
practice · easy · from Dynamic Programming

Climbing Stairs

time
O(n)
space
O(1)
tags
dynamic-programming · recursion

in the wild Counting paths through a state machine where each step has a fixed set of moves; the simplest 'cumulative count' DP that scales to any 1D recurrence.

Dynamic programming · 1D table fill

…
step 0 / 0

Problem

You're climbing a staircase with n steps. You can take 1 or 2 steps at a time. How many distinct ways can you climb to the top?

Examples

If you stare at the answers — 2, 3, 5, 8 — that's Fibonacci. The proof: the last step you take is either a 1 (preceded by some way to reach n-1) or a 2 (preceded by some way to reach n-2). So f(n) = f(n-1) + f(n-2).

Why this is the canonical first DP problem

Three solutions, in increasing sophistication:

  1. Naïve recursion. Direct translation of f(n) = f(n-1) + f(n-2) — but it re-solves the same subproblem exponentially many times. O(2^n).
  2. Memoized recursion. Same shape, but cache each call. O(n) time and space.
  3. Tabulation with rolling variables. Throw away the recursion entirely. Walk i from 2 to n, keeping only the last two values. O(n) time, O(1) space.

Climbing Stairs is the first DP problem every textbook teaches because it's the cleanest possible demonstration of the trade: the naïve recursion works but is unusably slow; memoization makes it fast; tabulation makes it both fast and tiny. Every other DP problem you'll see is some variant of this same pipeline.

Hints

Hint 1 — find the recurrence

What's the last step you took to reach n? It was either a 1 (coming from step n-1) or a 2 (coming from step n-2). So ways(n) = ways(n-1) + ways(n-2). What are the base cases?

Hint 2 — why naïve recursion explodes

To compute f(5) you need f(4) and f(3). To compute f(4) you need f(3) and f(2). Notice you compute f(3) twice. Then f(2) is computed 3 times. The tree of calls doubles at every level — exponential. The fix is caching.

Hint 3 — collapse to O(1) space

The recurrence only needs the previous two values. So instead of a full array, keep two integers a, b = 1, 2 and roll them: (a, b) = (b, a + b). After n - 1 iterations, b is the answer.

Solution

def climb_stairs(n: int) -> int:
    # Base cases bake the recurrence f(n) = f(n-1) + f(n-2) into two rolling vars.
    if n <= 2:
        return n
    a, b = 1, 2                       # f(1) = 1, f(2) = 2
    for _ in range(3, n + 1):
        a, b = b, a + b               # roll forward
    return b

cases = [(1, 1), (2, 2), (3, 3), (4, 5), (5, 8), (10, 89), (45, 1836311903)]
for n, expected in cases:
    got  = climb_stairs(n)
    mark = "✓" if got == expected else "✗"
    print(f"{mark} climb_stairs({n}) = {got}  (expected {expected})")
function climbStairs(n) {
  if (n <= 2) return n;
  let a = 1, b = 2;
  for (let i = 3; i <= n; i++) {
    const next = a + b;
    a = b;
    b = next;
  }
  return b;
}

const cases = [[1, 1], [2, 2], [3, 3], [4, 5], [5, 8], [10, 89], [45, 1836311903]];
for (const [n, expected] of cases) {
  const got = climbStairs(n);
  console.log(`${got === expected ? "✓" : "✗"} climbStairs(${n}) = ${got}  (expected ${expected})`);
}
pub fn climb_stairs(n: u32) -> u64 {
    if n <= 2 { return n as u64; }
    let (mut a, mut b): (u64, u64) = (1, 2);
    for _ in 3..=n {
        let next = a + b;
        a = b;
        b = next;
    }
    b
}

fn main() {
    let cases: &[(u32, u64)] = &[
        (1, 1), (2, 2), (3, 3), (4, 5), (5, 8), (10, 89), (45, 1_836_311_903),
    ];
    for (n, expected) in cases {
        let got  = climb_stairs(*n);
        let mark = if got == *expected { "✓" } else { "✗" };
        println!("{mark} climb_stairs({}) = {}  (expected {})", n, got, expected);
    }
}
#include <cstdint>
#include <iostream>

std::uint64_t climb_stairs(int n) {
    if (n <= 2) return n;
    std::uint64_t a = 1, b = 2;
    for (int i = 3; i <= n; ++i) {
        std::uint64_t next = a + b;
        a = b;
        b = next;
    }
    return b;
}

int main() {
    std::pair<int, std::uint64_t> cases[] = {
        {1, 1}, {2, 2}, {3, 3}, {4, 5}, {5, 8}, {10, 89}, {45, 1836311903ULL},
    };
    for (auto& [n, expected] : cases) {
        auto got = climb_stairs(n);
        std::cout << (got == expected ? "✓" : "✗")
                  << " climb_stairs(" << n << ") = " << got
                  << "  (expected " << expected << ")\n";
    }
}
#include <stdio.h>
#include <stdint.h>

uint64_t climb_stairs(int n) {
    if (n <= 2) return (uint64_t)n;
    uint64_t a = 1, b = 2;
    for (int i = 3; i <= n; i++) {
        uint64_t next = a + b;
        a = b;
        b = next;
    }
    return b;
}

int main(void) {
    int       ns []  = {1, 2, 3, 4, 5, 10, 45};
    uint64_t  exp[]  = {1, 2, 3, 5, 8, 89, 1836311903ULL};
    for (int i = 0; i < 7; i++) {
        uint64_t got = climb_stairs(ns[i]);
        printf("%s climb_stairs(%d) = %llu  (expected %llu)\n",
               got == exp[i] ? "✓" : "✗", ns[i],
               (unsigned long long)got, (unsigned long long)exp[i]);
    }
    return 0;
}

Three lines of state, one rolling update — that's it. The space-optimized form is more useful than it looks: every 1D DP problem whose recurrence depends on a constant-bounded history (Fibonacci, climb-stairs, house-robber, decode-ways) collapses to O(1) space the same way.

Complexity

Time
O(n) — one pass, O(1) work per step.
Space
O(1) — two rolling integers replace the full table.
Naïve recursion
O(2^n) — same subproblem solved exponentially many times. Memoization recovers O(n).
O(log n) via matrix exponentiation
Fibonacci can be computed in O(log n) via [[1,1],[1,0]]^n. Rare to need unless n is enormous.

In the wild

Variations