Climbing Stairs

1. Problem & Core Objective

You are climbing a staircase of n steps. Each move takes 1 or 2 steps. How many distinct ways can you reach the top?

n = 2  →  2      (1+1, 2)
n = 3  →  3      (1+1+1, 1+2, 2+1)
n = 5  →  8

Constraints: 1 <= n <= 45

What's actually being tested: the entire DP pipeline on the simplest possible recurrence. Recursion → memoise → tabulate → roll to O(1). Every other question in this section is this progression with a harder recurrence.

2. First-Principles Thought Process

Work backwards from the last move

To stand on step n, your final move came from step n−1 (a 1-step) or step n−2 (a 2-step). Those are the only options, and they're mutually exclusive — a path ends with exactly one of them.

So:

ways(n) = ways(n − 1) + ways(n − 2)

That's Fibonacci, with ways(1) = 1 and ways(2) = 2.

Reasoning from the last move is the general technique. "What was the final decision, and what state did it come from?" turns a counting problem into a recurrence.

Why the naive recursion is exponential

ways(5) calls ways(4) and ways(3); ways(4) calls ways(3) again. The tree has about 2^n nodes for n distinct subproblems.

That gap — exponentially many calls, linearly many distinct inputs — is the signal for DP.

The two properties that license DP

1. Optimal substructure — the answer is built from answers to smaller inputs.
2. Overlapping subproblems — the same smaller input recurs.

Without (2) it's plain divide and conquer, and caching buys nothing. Merge sort has (1) but not (2).

The four stages

Each is mechanical once the recurrence exists. The final stage is possible here because dp[i] reads a fixed window — just dp[i−1] and dp[i−2] — so two variables replace the array.

3. Solution Paths

Approach 1 — Plain recursion

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

• Time O(2^n) · Space O(n) stack

Counter-questions on this approach

⭐ "Why is this exponential when there are only n distinct inputs?"

Because nothing is remembered. climbStairs(3) is computed once inside the n−1 branch and again inside the n−2 branch, and each of those recomputes everything below it.

The call tree has roughly 2^n nodes while the distinct arguments number n. At n = 45 that's about 3.5 × 10^13 calls — hours.

⭐ "What exactly makes caching valid here?"

climbStairs(k) depends only on k — no hidden state, no path history. So the answer for a given k is the same every time it's asked, and storing it is sound.

That's a genuine precondition. If the function also depended on, say, which steps had been used, the argument alone wouldn't identify the subproblem and a simple cache would be wrong.

"Why if (n <= 2) return n?"

It folds both base cases: one step has 1 way, two steps have 2. Writing them separately is equally fine and arguably clearer.

Approach 2 — Memoised recursion (top-down)

public int climbStairs(int n) {
    return climb(n, new int[n + 1]);
}

private int climb(int n, int[] memo) {
    if (n <= 2) return n;
    if (memo[n] != 0) return memo[n];             // already computed
    return memo[n] = climb(n - 1, memo) + climb(n - 2, memo);
}

• Time O(n) · Space O(n) array plus O(n) stack

Counter-questions on this approach

⭐ "Why does one cache line collapse O(2^n) to O(n)?"

Each distinct n is now computed once; every later request is a lookup. There are n distinct arguments, so n real computations plus O(1) work each.

The recursion tree is effectively pruned to a path: every node is either a first visit (does work) or a cache hit (returns immediately).

⭐ "Is memo[n] != 0 a safe 'already computed' test?"

Here yes, because the answer is always >= 1 — there's at least one way to climb any positive number of steps, so 0 can never be a legitimate cached value.

That's a check worth making explicitly, not assuming. In a problem where 0 is a valid answer — counting ways with a constraint that might be unsatisfiable — this sentinel would cause infinite recomputation. Then you'd use Integer[] with null, or a separate boolean[] computed.

"Still O(n) stack. Does that matter at n = 45?"

No — 45 frames is nothing. But the tabulated version has no stack at all, and for a problem with n = 10^5 the recursion would overflow. Worth knowing the progression continues.

Approach 3 — Tabulation (bottom-up)

public int climbStairs(int n) {
    if (n <= 2) return n;
    int[] dp = new int[n + 1];
    dp[1] = 1; dp[2] = 2;
    for (int i = 3; i <= n; i++) dp[i] = dp[i - 1] + dp[i - 2];
    return dp[n];
}

• Time O(n) · Space O(n)

Counter-questions on this approach

⭐ "What's gained over memoisation?"

No recursion, so no stack and no call overhead. And the fill order is explicit — i ascending guarantees dp[i−1] and dp[i−2] are ready when needed, rather than relying on the recursion to discover that.

Getting the fill order right is the one thing tabulation asks of you that memoisation handles automatically.

"Are the base cases still needed?"

Yes, and they're the same ones. dp[1] and dp[2] are seeded because the recurrence can't produce them — dp[2] would read dp[0], which has no meaning here.

You could define dp[0] = 1 (one way to climb zero steps: do nothing) and seed only dp[1] = 1. That's cleaner and generalises better, though n <= 2 still needs handling if the array is sized n + 1.

Approach 4 — Rolling variables (optimal)

public int climbStairs(int n) {
    if (n <= 2) return n;
    int twoBack = 1, oneBack = 2;                 // dp[1], dp[2]

    for (int i = 3; i <= n; i++) {
        int current = oneBack + twoBack;
        twoBack = oneBack;
        oneBack = current;
    }
    return oneBack;
}

Trace — n = 5:

Answer 8 ✓

• Time O(n) · Space O(1)

Counter-questions on this approach

⭐ "When can you roll an array into variables?"

When the recurrence reads a fixed window of previous cells. Here dp[i] needs only dp[i−1] and dp[i−2], so two variables suffice and everything older is dead.

The counterexample matters: in Longest Increasing Subsequence, dp[i] reads every dp[j] for j < i, so nothing can be discarded and the array is required.

That's the test — fixed window rolls, unbounded lookback doesn't.

⭐ "Why does the update order matter?"

twoBack = oneBack must happen after current is computed, or current would read the already-overwritten value. Saving current first and shifting afterwards is the standard three-line shuffle.

Getting it wrong produces a plausible but wrong sequence — it would compute dp[i] = 2·dp[i−1], giving powers of two.

"Could the result overflow?"

climbStairs(45) is Fibonacci(46) = 1,836,311,903, which fits in int with about 15% headroom. At n = 47 it would overflow.

The constraint stopping at 45 is not a coincidence — it's chosen precisely so int suffices. Worth noticing rather than assuming.

"Is there an O(log n) solution?"

Yes — matrix exponentiation of [[1,1],[1,0]], or Binet's closed form. Both are O(log n) and genuinely faster asymptotically. At n = 45 they're slower in practice, and Binet's floating-point error makes it unreliable for large n. Worth naming, not worth writing.

Comparison

4. Why the Optimal Wins

The recursion recomputes the same n subproblems exponentially many times. Memoisation removes the repetition, tabulation removes the recursion, and rolling removes the array.

Each step is mechanical. The only judgement is the last one — recognising that the recurrence reads a fixed window, so all but two cells are dead.

The framing worth keeping:

Reason from the last move: what was the final decision, and what state preceded it? Then: recursion → memoise → tabulate → roll. Roll only when the recurrence reads a fixed window of previous cells.

5. Java Prerequisites

The memo sentinel

if (memo[n] != 0) return memo[n];

Valid only when 0 can't be a legitimate answer. Otherwise use Integer[] with null, or a boolean[] computed.

Assign-and-return

return memo[n] = climb(n-1, memo) + climb(n-2, memo);

Java assignment is an expression, so this stores and returns in one line.

The rolling shuffle — order matters:

int current = oneBack + twoBack;
twoBack = oneBack;
oneBack = current;

Overflow — Fibonacci(46) is about 1.8 × 10^9, just inside int. At n = 47 you'd need long.

6. Interview Communication Guide

Clarifying questions: Steps of exactly 1 or 2 (yes)? Are 1+2 and 2+1 different ways (yes — order matters)? What's the maximum n (45 — and that's chosen so int suffices)? Is n = 0 possible (no, n >= 1)?

The pitch

"I'd reason from the last move. To be on step n, the final move came from n−1 or n−2 — those are the only options and they're mutually exclusive. So ways(n) = ways(n−1) + ways(n−2), which is Fibonacci with ways(1) = 1 and ways(2) = 2.

Written as plain recursion that's O(2^n) — about 3.5 × 10^13 calls at n = 45 — because ways(3) gets recomputed in both branches and everything below it with it.

But there are only n distinct subproblems. That gap between exponentially many calls and linearly many distinct inputs is the signal for DP.

So: memoise, which collapses it to O(n) with one cache line. Then tabulate bottom-up, which removes the recursion and makes the fill order explicit. Then roll — dp[i] reads only dp[i−1] and dp[i−2], a fixed window, so two variables replace the array and it's O(1) space.

That last step only works because the lookback is bounded. In Longest Increasing Subsequence, dp[i] reads every earlier cell, so nothing can be discarded.

One detail on the memo: I test memo[n] != 0 as 'already computed', which is safe here because the answer is always at least 1. In a problem where 0 is a legitimate answer that sentinel would cause infinite recomputation, so it's worth checking rather than assuming.

O(n) time, O(1) space. There's an O(log n) matrix-exponentiation solution, but at n = 45 it's slower in practice."

Edge cases to volunteer:

Name n = 45. It's the constraint boundary and it's chosen precisely so the answer fits in int — noticing that shows you checked the arithmetic rather than assuming.

7. Follow-Up Questions — Modified Constraints

⭐ "What if you could take 1, 2, or 3 steps?"

dp[i] = dp[i-1] + dp[i-2] + dp[i-3] — the Tribonacci sequence. Three rolling variables instead of two. The window is still fixed, so O(1) space holds.

⭐ "What if each step had a cost and you wanted the cheapest climb?"

Question 2 — Min Cost Climbing Stairs. min replaces +, and the recurrence adds the step's own cost. Same shape, different combiner: counting uses +, optimisation uses min or max.

"What if certain steps were broken and couldn't be used?"

dp[i] = 0 for a broken step — zero ways to stand there — and the recurrence handles the rest. Note the memo sentinel breaks here, since 0 becomes a legitimate answer, which is exactly the case flagged above.

"What if n were 10^5?"

The rolling version is O(n) and fine, but the result overflows int long before that — Fibonacci grows exponentially. You'd need BigInteger, or the problem would ask for the answer modulo some prime, which keeps it in int.

"Return the actual sequences, not the count."

That's backtracking, not DP — there are exponentially many, so enumerating them is O(2^n) regardless. Counting and listing have genuinely different complexities, which is worth stating rather than promising to extend the DP.

"What if you could take any number of steps from a given set?"

dp[i] = sum of dp[i − s] over each allowed step s. That's the coin change counting problem, and the window is fixed only if the step set is bounded — which is what makes it still rollable.