Climbing Stairs

You're climbing a staircase with N steps. Each time you can take 1 or 2 steps. How many distinct ways to reach the top? This is Fibonacci in disguise — and the first "real" DP problem you'll encounter on every platform.

The Insight

To reach step i, you must have come from step i−1 (one step) or step i−2 (two steps). So the number of ways to reach step i is the sum of ways to reach i−1 and i−2. Base cases: step 1 has 1 way, step 2 has 2 ways (1+1 or 2).

C++ — O(N) time, O(1) space

int climb_stairs(int n) {
    if (n <= 2) return n;
    int a = 1, b = 2;  // ways[1], ways[2]
    for (int i = 3; i <= n; i++) {
        int c = a + b;
        a = b;
        b = c;
    }
    return b;
}

Rust — O(N) time, O(1) space

fn climb_stairs(n: i32) -> i32 {
    if n <= 2 { return n; }
    let (mut a, mut b) = (1, 2);
    for _ in 3..=n {
        let c = a + b;
        a = b;
        b = c;
    }
    b
}

💡 Generalised climbing

If you can take steps of sizes [1, 3, 5], then ways[i] = ways[i-1] + ways[i-3] + ways[i-5]. The recurrence generalises: ways[i] = sum of ways[i - step] for each step size. This is the template for the "coin change" problem later.

Key Takeaways

→ Climbing stairs = Fibonacci (shifted by one).
→ Recurrence: dp[i] = dp[i-1] + dp[i-2] — O(N) time, O(1) space.
→ For general step sets: dp[i] = sum(dp[i - s]) for each step s.

The Insight

C++ — O(N) time, O(1) space

Rust — O(N) time, O(1) space

Key Takeaways

Practice