67. Climbing Stairs

The first move from step 0 is either +1 (then we still need f(n-1) ways to finish from step 1) or +2 (then we need f(n-2) ways from step 2). So f(n) = f(n-1) + f(n-2) — Fibonacci. Direct recursion captures the recurrence but pays for it: it re-solves the same subproblems exponentially many times.

The recurrence

f(n) = f(n-1) + f(n-2) with base cases f(1) = 1, f(2) = 2.

Why f(2) = 2? You can climb (1, 1) or (2). Two ways.

Steps

1. Base case: if n <= 2, return n.
2. Else return climbStairs(n - 1) + climbStairs(n - 2).

Walk-through

climbStairs(5) expands as:

f(5) = f(4) + f(3)
     = (f(3) + f(2)) + (f(2) + f(1))
     = ((f(2) + f(1)) + 2) + (2 + 1)
     = ((2 + 1) + 2) + 3
     = 5 + 3
     = 8

Why exponential

Each call branches into two more calls of nearly the same size, so the call-tree size grows like 2ⁿ. Concretely, climbStairs(30) makes over a million calls — already slow.

Complexity

• Time: O(2ⁿ).
• Space: O(n) recursion depth.

class Solution {
    public int climbStairs(int n) {
        if (n <= 2) return n;
        return climbStairs(n - 1) + climbStairs(n - 2);
    }
}

The recurrence f(n) = f(n-1) + f(n-2) only ever depends on the previous two values. So instead of an array dp[0..n] we just keep two scalars and slide them forward.

Steps

1. If n <= 2, return n.
2. Initialise a = f(1) = 1, b = f(2) = 2.
3. For i from 3 to n: compute the next value as a + b, then shift: a, b = b, a + b.
4. Return b.

Walk-through

n = 5. Initial a, b = 1, 2.

Return b = 8. ✓

Why two variables suffice

The recurrence is first-order in the past — only f(n-1) and f(n-2) are needed. So we never need to remember anything older. That's the standard space-optimisation for any "depends on last k" DP.

Edge cases

• n = 1: return 1 (only one way: take a single step).
• n = 2: return 2.

Complexity

• Time: O(n) — single linear loop.
• Space: O(1) — two scalars.