LeetCode · #70

Climbing Stairs Solution

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

Section One · Problem

Problem Statement

🏷️

Difficulty

Easy

🔗

LeetCode

Problem #70

🏗️

Pattern

DP — 1D Fibonacci recurrence

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

Example

 Input: n = 3 Output: 3 // 1+1+1, 1+2, 2+1 — three distinct ways 

Constraints

• 1 ≤ n ≤ 45 ← fits in int; O(n) required, O(2ⁿ) TLE

Section Two · Approach 1

Recursion — O(2ⁿ)

At each step, you have two choices: climb 1 or climb 2. Recursively count all paths: ways(n) = ways(n-1) + ways(n-2). Base cases: ways(0)=1, ways(1)=1.

Why it works

The recurrence correctly partitions all paths by the first move: paths that start with a 1-step + paths that start with a 2-step. Base cases represent "already at the top" (1 way).

Why we can do better

Problem: The recursion tree branches exponentially — ways(n) recomputes ways(n-2) twice, ways(n-3) three times, etc. Total calls: O(2ⁿ). For n=45 that's ~35 billion calls. Memoization or bottom-up DP brings this to O(n) by storing each subproblem once.

Java — Naive recursion

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

Python — Naive recursion

 class Solution:
def climbStairs(self, n: int) -> int:
if n <= 1: return 1 return self.climbStairs(n-1) + self.climbStairs(n-2)

Metric	Value
Time	O(2ⁿ) — exponential recursion tree
Space	O(n) — recursion depth

Section Three · Approach 2

Bottom-Up DP / Fibonacci — O(n) time, O(1) space

The recurrence dp[i] = dp[i-1] + dp[i-2] is exactly the Fibonacci sequence. Since each state depends only on the previous two, we only need two variables — no array required.

💡 Mental model: Imagine you're standing on a staircase and looking down. The number of ways to reach your current step equals "ways if I got here with a 1-step" plus "ways if I got here with a 2-step." That's just the ways to reach the step below me plus the step two below me. You only need to remember the last two answers as you walk up — like a caterpillar inching forward with two legs, always dropping the back leg and growing a new front one.

Algorithm — two-variable Fibonacci

Initialize a = 1 (ways to step 0), b = 1 (ways to step 1).
For i from 2 to n: temp = a + b; a = b; b = temp.
Return b — the number of ways to reach step n.

🎯 When to recognize this pattern:

Any time dp[i] depends on a fixed number of previous states, you can reduce O(n) space to O(1) by keeping only those states in variables.
This "rolling variables" optimization applies to LC 198 (House Robber), LC 746 (Min Cost Climbing Stairs), and any Fibonacci-like recurrence.
The signal: "dp[i] = f(dp[i-1], dp[i-2])."

Why this is Fibonacci and not combinatorics:

You might try to count paths using C(n,k) combinations, but the number of 2-steps k can range from 0 to ⌊n/2⌋, and each k gives C(n-k, k) arrangements.
Summing these is more complex and error-prone than the DP approach.
The Fibonacci recurrence subsumes all these cases automatically.

Section Four · Trace

Visual Walkthrough

Trace for n = 5. Building dp bottom-up with two variables.

Climbing Stairs — Fibonacci DP (n=5)

Section Five · Implementation

Code — Java & Python

Java — Two-variable Fibonacci

 class Solution {
public int climbStairs(int n) {
int a = 1, b = 1; // dp[0]=1, dp[1]=1 for (int i = 2; i <= n; i++) {
int tmp = a + b; // dp[i] = dp[i-2] + dp[i-1]
a = b; // slide window forward
b = tmp;
        }
return b;
    }
}

Python — Two-variable Fibonacci

 class Solution:
def climbStairs(self, n: int) -> int:
        a, b = 1, 1 # dp[0], dp[1] for _ in range(2, n + 1):
            a, b = b, a + b # simultaneous swap — no temp needed return b

Section Six · Analysis

Complexity Analysis

Approach	Time	Space	Trade-off
Naive recursion	O(2ⁿ)	O(n)	Exponential — TLE at n ≥ ~30
Memoized recursion	O(n)	O(n)	Top-down DP array; correct but uses O(n) space
Two-variable Fibonacci ← optimal	O(n)	O(1)	Only two variables; minimal code; constant space

Can we do better than O(n)?:

Yes — matrix exponentiation gives O(log n) by raising the Fibonacci transformation matrix to the nth power.
But for n ≤ 45, the constant-factor overhead of matrix multiplication makes O(n) faster in practice.
The O(log n) approach is academic — interviewers rarely expect it.

Section Seven · Edge Cases

Edge Cases & Pitfalls

Case	Input	Why It Matters
n = 1	`1`	Only one step — one way. Loop doesn't execute. Return b=1.
n = 2	`2`	Two ways: 1+1 or 2. One loop iteration. b=2.
n = 0	Not in constraints	Constraints say n ≥ 1. But if allowed, answer is 1 (already at top).
n = 45 (max)	`45`	Fib(46) = 1,836,311,903 — fits in int (max ~2.1 billion). No overflow.
Off-by-one in loop	any	Loop must run from 2 to n (inclusive). Running to n-1 gives dp[n-1] instead of dp[n].
Swapping order wrong	any	If you update a before computing a+b, the sum uses the wrong (already updated) a value.

⚠ Common Mistake: Writing a = b; b = a + b; instead of using a temp variable (Java) or simultaneous swap (Python). The first line overwrites a with b, and then the second line computes b + b instead of old_a + b. In Java, use int tmp = a+b; a = b; b = tmp;. In Python, use a, b = b, a+b — the right side is fully evaluated before assignment.

← Back to DP — 1D problems

LearningTree

LC 70 · Climbing Stairs — Solution & Explanation | DSA Guide