p05 — Climbing Stairs

Source: LeetCode 70 · Easy · Topics: Math, DP, Memoization Companies: Adobe (high), Amazon (medium), Apple (medium) Loop position: the canonical “intro to DP” — almost always a warmup before a real DP question

1. Quick Context

The “Fibonacci in disguise” problem. It’s the cleanest possible 1D DP and exists to teach you the recipe: (1) define state, (2) write recurrence, (3) identify base cases, (4) decide order, (5) compress space. If you can’t articulate those 5 steps on p05, you can’t on p51 (House Robber), p55 (Jump Game), p60 (Longest Increasing Subsequence), or anywhere else.

What it looks like it tests: ability to recognize Fibonacci. What it actually tests: the DP recipe. Interviewers use this as a calibration — if you write recursion without memoization (O(2^N)), or memoization without realizing iteration is simpler, you’ve revealed your DP fluency level.

2. LeetCode Link + Attempt Gate

🔗 https://leetcode.com/problems/climbing-stairs/

10-min timer. Cold attempt. If you reach for recursion-without-memo, that’s the signal you need this rep most.

3. Prerequisite Concepts

  • Recursion + memoization basics — phase-01 §8
  • “State + recurrence + base case” — the universal DP recipe
  • Space compression: when only the last k states are needed, store only those

4. How to Approach

Restate: From step 0, reach step n, taking either 1 or 2 steps at a time. How many distinct ways?

Clarify:

  • “Distinct sequences of moves, or distinct step sets?” (Sequences — 1+2 and 2+1 are different. ASK; some problems differ.)
  • “n ≥ 1?” (Per LC: 1 ≤ n ≤ 45.)
  • “Why n ≤ 45?” (Hints at int overflow in some languages; in Python no issue. Worth a verbal acknowledgment.)

Examples:

  • n=1 → 1 (just [1])
  • n=2 → 2 ([1,1], [2])
  • n=3 → 3 ([1,1,1], [1,2], [2,1])
  • n=4 → 5 (Fibonacci pattern starts to emerge: 1, 2, 3, 5)
  • n=5 → 8

Brute force (recursive): f(n) = f(n-1) + f(n-2), base f(1)=1, f(2)=2. O(2^N) time without memo — exponential.

Pattern recognition: The recurrence is Fibonacci. Anywhere you see “ways to reach state N built from prior states” with overlapping subproblems → DP.

Optimal: Iterative DP, two scalars (prev1, prev2). O(N) time, O(1) space.

if n <= 2: return n
prev2, prev1 = 1, 2     # f(1), f(2)
for i in range(3, n+1):
    prev2, prev1 = prev1, prev1 + prev2
return prev1

Recurrence justification: To reach step n, the last move was either a 1-step (from step n-1) or a 2-step (from step n-2). These are disjoint sets of paths, so total = f(n-1) + f(n-2).

5. Progressive Hints

hints.md. One at a time.

6. Deeper Insight — Why It Works

The DP recipe applied:

  1. State: f(n) = number of distinct ways to reach step n.
  2. Recurrence: f(n) = f(n-1) + f(n-2) (last move was 1 or 2).
  3. Base cases: f(1) = 1, f(2) = 2. (Why two base cases? Recurrence reaches back two steps; we need both grounded.)
  4. Order: Bottom-up (iteratively i = 3 .. n) because f(n) depends only on smaller i.
  5. Space compression: Only the last two values are needed, so two scalars suffice — O(1) space.

Why two base cases, not one? The recurrence f(n) = f(n-1) + f(n-2) requires f(n-2) to be defined when n=3, so we must specify both f(1) and f(2). Trying to derive f(2) from f(0) + f(1) requires defining f(0) = 1 (the empty path) — a valid alternative formulation, but the natural problem space starts at step 1.

Closed form (Staff signal): Fibonacci has a closed-form Φ^n / √5 (Binet’s formula). For interview purposes, mention it exists but don’t compute it — floating-point loses precision for n > ~70 and the problem caps at 45 anyway.

Matrix exponentiation (Staff signal): Fibonacci can be computed in O(log N) via [[1,1],[1,0]]^n. Overkill for n ≤ 45; useful when n is large or when the recurrence generalizes (e.g., f(n) = a·f(n-1) + b·f(n-2)).

7. Anti-Pattern Analysis

Wrong #1 — Plain recursion, no memo:

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

O(2^N). At n=45, ~35 billion calls. TLE for sure. Interviewer’s note: “didn’t recognize overlapping subproblems.”

Wrong #2 — Memo with dict overhead:

@lru_cache
def climb(n):
    if n <= 2: return n
    return climb(n-1) + climb(n-2)

Works in O(N) but uses O(N) call stack and dict memory. Iterative is strictly better — no recursion limit risk, O(1) space. Mention lru_cache exists but show why iterative wins.

Wrong #3 — DP table O(N) space:

dp = [0]*(n+1)
dp[1], dp[2] = 1, 2
for i in range(3, n+1): dp[i] = dp[i-1] + dp[i-2]
return dp[n]

Correct, O(N) time, O(N) space. Misses the O(1) compression. Senior signal: notice you only need the last 2 values, drop the array.

Wrong #4 — Off-by-one on base cases: Forgetting n==1 returns 1, not 2; or forgetting to handle n==2 directly and letting the loop run. Tests with n=1, 2, 3 catch these.

8. Skills & Takeaways

The DP recipe — burn it in:

  1. State definition
  2. Recurrence with justification
  3. Base cases (one per step the recurrence reaches back)
  4. Computation order
  5. Space compression (only keep what’s referenced)

Generalizations — variants you’ll see:

  • LC 746 — Min Cost Climbing Stairs (same structure, minimize cost instead of count)
  • LC 198 — House Robber (same structure with “can’t be adjacent” constraint)
  • LC 213 — House Robber II (circular variant)
  • LC 91 — Decode Ways (Fibonacci with validity guards)
  • LC 1137 — N-th Tribonacci (extend recurrence to 3 prior terms)
  • LC 509 — Fibonacci Number (literal Fibonacci)

When you can take 1, 2, or 3 steps: f(n) = f(n-1) + f(n-2) + f(n-3) (Tribonacci). When you can take 1..k steps: f(n) = sum f(n-i) for i=1..k → can be O(N) with a sliding window.

9. When to Move On

  • Solved iteratively, O(N) time, O(1) space, <8 min
  • Tested n=1, n=2, n=3
  • Articulated all 5 DP recipe steps without prompting
  • Connected to House Robber (LC 198) as the same pattern with cost
  • Stress test passes
  • Mentioned closed-form / matrix exp exist (Staff signal)

10. Company Context

Adobe (this is their go-to DP warmup)

  • Frame: Often given verbatim.
  • What they want: Iterative O(1) space, articulated DP recipe. Recursion without memo is a near-instant fail.
  • Extension: “What if you can take 1, 2, or 3 steps?” → Tribonacci. Tests generalization.

Amazon

  • Frame: Sometimes as a paving / tiling problem (“ways to tile a 1×N corridor with 1×1 and 1×2 tiles”) — same Fibonacci underneath.
  • Extension: “Now there’s a step you can’t land on (broken stair).” → DP with constraint: f(broken) = 0, recurrence unchanged otherwise.

Apple

  • Frame: Often paired with LC 198 (House Robber) — they want to see if you generalize.

11. Interviewer’s Lens

PhaseStrongWeakScorecard
ReadingAsks “sequences vs sets” + clarifies n boundsDives in“Verifies the contract”
Pre-codingNames the recurrence with justificationSays “I’ll recurse”“Articulates DP structure”
CodingIterative + 2 scalarsRecursive without memo“Optimal space upfront”
Edgen=1, n=2 coveredMisses n=1“Catches base-case bugs”
FinishMentions DP recipe steps + extensionsSays “done”“Frameworks generalize”

12. Level Delta

LevelAnswer
MidIterative O(N), O(1). Works. ~8 min.
Senior+ states the 5-step DP recipe explicitly + tests n=1,2,3 + offers to extend to k-step.
Staff+ mentions closed-form (Binet) and matrix exponentiation as O(log N) alternatives + connects to House Robber as same family with different reduction operator (sum → max).
Principal+ asks production context (“counting paths in an event graph? combinatorics for a recommender?”) + identifies that for very large n we need modular arithmetic (problem caps prevent overflow but real systems don’t) + suggests matrix exponentiation under modulo for n in the millions.

13. Follow-up Questions & Full Answers

Q1: “What if you can take 1, 2, or 3 steps?”

Answer: Tribonacci. f(n) = f(n-1) + f(n-2) + f(n-3), base cases f(1)=1, f(2)=2, f(3)=4. O(N) time, O(1) space with three scalars.

Q2: “What if you can take 1..k steps?”

Answer: f(n) = sum f(n-i) for i in 1..k. Naive O(N·k). Optimize via sliding window: f(n) = f(n-1) + f(n-1) - f(n-1-k) (because consecutive windows overlap in k-1 terms). O(N), O(k) space.

Q3: “Now some steps are broken — you can’t land there.”

Answer: f(broken[i]) = 0. Recurrence unchanged. Still O(N), O(1) — just a guard inside the loop.

Q4: “Same problem but n can be up to 10^18.”

Answer: Matrix exponentiation. [f(n), f(n-1)]^T = M^(n-1) · [f(1), f(0)]^T where M = [[1,1],[1,0]]. Compute M^(n-1) via binary exponentiation in O(log N) matrix multiplications, each O(1) for a 2×2 matrix. Total O(log N). Use modular arithmetic to prevent overflow.

Q5: “How do you test it?”

Answer: (1) Small cases against hand-computed Fibonacci values (1, 2, 3, 5, 8, 13). (2) Property: brute recursive (with memoization) vs iterative agree on n in 1..30. (3) Stress on the boundary n=1 (off-by-one trap) and n=45 (max constraint).

14. Full Solution Walkthrough

See solution.py.

  • climb_brute(n): plain recursion, no memo. Used as oracle for small n only (would TLE for large).
  • climb(n): iterative two-scalar version. O(N) time, O(1) space.
  • climb_memo(n): top-down memoization, included for comparison. O(N) time, O(N) space.
  • stress_test: brute vs optimal vs memo on n ∈ [1, 25], all three agree.

15. Beyond the Problem

Real systems this is the kernel of:

  • Path-counting in DAGs: number of distinct routes through a graph. The 1D variant generalizes to the topological order of a DAG.
  • State-machine reachability: number of distinct token sequences leading to a state in a parser.
  • Combinatorial enumeration in recommender systems: counting compatible item sequences under constraints.
  • Probabilistic state aggregation: when transition probabilities are uniform, counts and probabilities differ only by a normalizing constant.

Principal-engineer code review: “This function is correct but its name climb_stairs is so specific that it won’t be reused. The underlying primitive — counting paths under additive recurrence — appears in three other places in our codebase, each reimplemented. Extract count_paths(n, allowed_step_sizes) and use it everywhere. Also: cache the result if called repeatedly with the same n — but for n ≤ 45 the compute cost is negligible, so probably not worth the cache complexity.”