Climbing Stairs (LC 70)

Pattern: 1-D DP (Fibonacci recurrence) Difficulty: Easy Key Concept: Ways to reach step n = ways to reach n-1 + ways to reach n-2.

Problem Statement

You are climbing a staircase. It takes n steps to reach the top. Each move you can climb 1 or 2 steps. Return the number of distinct ways to reach the top.

Example

• n = 2 → 2 (1+1, 2)
• n = 3 → 3 (1+1+1, 1+2, 2+1)

---

1. Algorithm & Pseudocode

Brute force (recursive)

ways(n):
  if n <= 1: return 1
  return ways(n-1) + ways(n-2)

This is exponential ((O(2^n))) because of overlapping subproblems.

Optimal (Bottom-up DP)

1. prev2 = 1 (ways(0)), prev1 = 1 (ways(1)).
2. For i = 2..n: curr = prev1 + prev2; shift prev2 = prev1; prev1 = curr.
3. Return prev1.

---

2. Step-by-Step Analysis

Why the recurrence is correct The very last step you took was either 1 step (you came from step n-1) or 2 steps (you came from n-2). Those are disjoint groups of paths, so add their counts.

Why bottom-up DP Each ways(i) only needs ways(i-1) and ways(i-2) — we don’t need a full array, just two rolling variables.

Boundary ways(0) = 1 (one way: stand still). ways(1) = 1 (one way: 1 step).

ASCII Trace for n = 5

i:      0  1  2  3  4  5
ways:   1  1  2  3  5  8
                       └─ answer

---

3. The Dry Run

n = 5

i	prev2 (i-2)	prev1 (i-1)	curr = prev1 + prev2
2	1	1	2
3	1	2	3
4	2	3	5
5	3	5	8

Return 8.

---

4. Java Solution

Brute Force

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

Time: (O(2^n)) Space: (O(n)) call stack

Optimal

class Solution {
    public int climbStairs(int n) {
        if (n <= 1) return 1;
        int prev2 = 1, prev1 = 1;
        for (int i = 2; i <= n; i++) {
            int curr = prev1 + prev2;
            prev2 = prev1;
            prev1 = curr;
        }
        return prev1;
    }
}

Time: (O(n)) Space: (O(1))

---

5. The “Java vs. Others” Edge

• Java’s int is 32-bit; the answer for n = 45 is 1,836,311,903 — within int range. For larger n, switch to long.
• A memoized recursive solution would use Integer[] so null distinguishes “not computed” from 0.

---

6. Complexity Summary

Approach	Time	Space	Notes
Recursion	(O(2^n))	(O(n))	Exponential repetition
DP (array)	(O(n))	(O(n))	Tabulation
DP (rolling)	(O(n))	(O(1))	Two variables