129 — Climbing Stairs

129 — Climbing Stairs

LeetCode 70 · Easy. You are climbing a staircase. It takes n steps to reach the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

---

🍽️ Intuition

Stand at the bottom of an n-step staircase and ask: what's the very last hop that lands me on step n? There are only two possibilities — the last hop was a single step from step n-1, or the last hop was a double step from step n-2. Every distinct way of climbing the whole staircase ends in exactly one of those two ways, and the two groups don't overlap. So the total number of ways to reach step n is just the number of ways to reach step n-1 plus the number of ways to reach step n-2. That's it — that's the whole problem, once you stop thinking about "all the ways to climb" and start thinking about "the very last move."

---

🚩 Pattern-Recognition Cue

"In how many distinct ways can you reach the top?" is a counting question where each step's count is built from a small, fixed number of earlier counts — the textbook 1-D DP tell. The moment you notice the recurrence only ever looks back one or two positions (a Fibonacci shape), you know a rolling pair of variables will do the whole job.

---

🐢 Brute Force

Recompute the answer from scratch for every sub-staircase with plain recursion — no memoization, so the same smaller staircases get re-solved exponentially many times.

func climbStairsBruteForce(_ n: Int) -> Int {
    if n <= 2 { return n }
    return climbStairsBruteForce(n - 1) + climbStairsBruteForce(n - 2)
}

// smoke test
print(climbStairsBruteForce(2))    // 2
print(climbStairsBruteForce(3))    // 3
print(climbStairsBruteForce(5))    // 8

Big-O: O(2^n) time — the recursion tree branches in two at every level, and climbStairsBruteForce(n - 2) gets fully re-solved from within both the n - 1 and n - 2 branches above it. O(n) space for the recursion stack.

---

🚀 Optimal

Walk forward from step 1, keeping only the two most recent counts — no need to store the whole history once a count has been consumed by the next one.

func climbStairs(_ n: Int) -> Int {
    if n <= 2 { return n }

    var prev2 = 1   // ways to reach step 1
    var prev1 = 2   // ways to reach step 2

    for _ in 3...n {
        let current = prev1 + prev2
        prev2 = prev1
        prev1 = current
    }

    return prev1
}

// smoke test — same cases as the brute force
print(climbStairs(2))    // 2
print(climbStairs(3))    // 3
print(climbStairs(5))    // 8

Big-O: O(n) time — one pass from step 3 to step n, O(1) work per step. O(1) extra space — only two rolling variables, no array or recursion stack.

---

🔑 The Key Insight

Both versions rely on the exact same recurrence, ways(n) = ways(n-1) + ways(n-2) — the difference is entirely about remembering versus re-deriving. The brute force treats every call as if it were the first time anyone had ever asked "how many ways to reach step k?", so the same sub-answers get computed over and over, doubling the work at every level of the recursion tree. The optimal version notices that once ways(k) has been computed, it never needs to be recomputed — it just gets carried forward as prev1/prev2 and combined once. Collapsing exponential re-derivation into a single linear walk with two rolling variables is the entire jump from O(2^n) to O(n).

---

🔗 Related Chapters

• 1D Dynamic Programming — this problem is chapter 26's own worked example in miniature: a Fibonacci-shaped recurrence, dp[i] = dp[i-1] + dp[i-2], walked forward with two rolling variables instead of a full array.
• Arrays and Strings — even though the optimal solution drops the array entirely, the shape of the computation is a left-to-right tabulation sweep over positions 1...n, the same access pattern that motivates array-backed DP.

---

🧸 Memory Sentence

Climbing Stairs is pure Fibonacci in a staircase costume — the ways to reach step n are just the ways to reach step n-1 plus the ways to reach step n-2, remembered instead of recomputed.

---

✅ Check Your Understanding

1. Why does the brute-force recursion tree for climbStairsBruteForce(5) end up calling climbStairsBruteForce(2) multiple times, and how many total calls does that recursion make compared to the 3 loop iterations the optimal version needs?
2. The base case handles n <= 2 by returning n directly. Trace through why climbStairs(1) and climbStairs(2) both need to bypass the loop entirely rather than starting prev2/prev1 from some other values.
3. If a third move type were allowed — climbing 3 steps at once — which single line of the optimal solution would need to change, and would the space complexity stay O(1)?

---

⬅️ Previous: Cheapest Flights Within K Stops · Next: Min Cost Climbing Stairs ➡️