Climbing Stairs

Introduction

A staircase of $n$ steps. At each move you can hop one step or two. The question is plain: in how many distinct ways can you reach the top? Most candidates write a recursive solution in fifteen seconds and stop. That fifteen-second solution is exponential, and the gap between “obvious” and “good enough” is exactly why this problem keeps appearing.

This is the rite-of-passage problem for dynamic programming. Four approaches walk a careful arc — exponential recursion, memoized recursion, bottom-up sweep, and a matrix-exponentiation reframing — and each one teaches a distinct DP move that reappears across half a dozen later problems. The lesson isn’t the algorithm. It’s the discipline of asking, “my recursion is correct — what is it doing twice?”, and recognizing the answer.

The interview test isn’t writing the recurrence. It’s noticing what the recurrence is doing twice — and trading work for memory.

If you’re early in DP prep, walk all four approaches in order — the lessons compound. If you can write the bottom-up answer in your sleep, jump to the matrix-exponentiation section: it’s the unfamiliar one and the one most worth knowing.

What the interviewer is actually testing

1. Recurrence recognition. Can you state, in one sentence, why the answer for $n$ stairs equals the answer for $n-1$ plus the answer for $n-2$? Candidates who can’t articulate that miss the entire problem.
2. Awareness of overlapping subproblems. The naive recursion is correct; recognizing that it’s exponential because subproblems repeat is the DP pivot.
3. Space discipline. The bottom-up array is $O(n)$; collapsing to two variables is $O(1)$. Spotting that compression is a senior signal.
4. Knowing the next level. Matrix exponentiation isn’t required for this problem in most interviews — but mentioning it as the $O(\log n)$ option signals you’ve been deeper into algorithmics than the median candidate.

Problem statement

Clarifying questions — and why each one matters

A mental framework — the recurrence

Think of the very last hop. To stand on stair $n$, the previous position was either stair $n-1$ (and you took a 1-step) or stair $n-2$ (and you took a 2-step). Those are the only two cases — they don’t overlap, and together they cover everything.

So the number of ways to reach stair $n$ is the number of ways to reach stair $n-1$ plus the number of ways to reach stair $n-2$:

with base cases $f(0) = f(1) = 1$. That’s the entire algorithmic content. Everything in the rest of the chapter is how to evaluate this recurrence efficiently.

If the recurrence looks familiar, it should: $f$ is the Fibonacci sequence, shifted by one. The chapter’s four approaches are the standard four ways to evaluate Fibonacci, and the lessons transfer to every recurrence with the same “constant-state” shape.

Discussion

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

#include <vector>

namespace {
int solve(int n, std::vector<int>& memo) {
    if (n <= 1) return 1;
    if (memo[n] != -1) return memo[n];
    memo[n] = solve(n - 1, memo) + solve(n - 2, memo);
    return memo[n];
}
}  // namespace

int climbStairs(int n) {
    std::vector<int> memo(n + 1, -1);
    return solve(n, memo);
}

int climbStairs(int n) {
    if (n <= 1) return 1;
    int prev2 = 1;  // ways to climb 0 stairs
    int prev1 = 1;  // ways to climb 1 stair
    for (int i = 2; i <= n; ++i) {
        const int curr = prev1 + prev2;
        prev2 = prev1;
        prev1 = curr;
    }
    return prev1;
}

#include <array>
#include <cstdint>

namespace {

using Matrix = std::array<std::array<std::int64_t, 2>, 2>;

Matrix multiply(const Matrix& a, const Matrix& b) {
    return {{
        {a[0][0] * b[0][0] + a[0][1] * b[1][0],
         a[0][0] * b[0][1] + a[0][1] * b[1][1]},
        {a[1][0] * b[0][0] + a[1][1] * b[1][0],
         a[1][0] * b[0][1] + a[1][1] * b[1][1]},
    }};
}

Matrix power(Matrix base, int exp) {
    Matrix result = {{{1, 0}, {0, 1}}};  // identity
    while (exp > 0) {
        if (exp & 1) result = multiply(result, base);
        base = multiply(base, base);
        exp >>= 1;
    }
    return result;
}

}  // namespace

int climbStairs(int n) {
    if (n <= 1) return 1;
    const Matrix M = {{{1, 1}, {1, 0}}};
    const Matrix result = power(M, n);
    return static_cast<int>(result[0][0]);
}

Approach comparison

Default answer: the two-variable bottom-up sweep. State that out loud when you close.

Follow-ups to anticipate

Pattern recognition — constant-state DP

The move this chapter teaches — evaluate a recurrence whose state is a fixed-size window over previous values — is a recurring shape in dynamic programming:

• House Robber. $f(i) = \max(f(i-1), f(i-2) + \text{nums}[i])$. Same two-variable collapse.
• Best Time to Buy/Sell Stock. Two running values: best profit so far and minimum price so far. Constant state, linear sweep.
• Maximum Subarray (Kadane’s). Two running values: current ending sum and best ever. Same shape.
• Decode Ways (LC 91). $f(i)$ depends on $f(i-1)$ and $f(i-2)$ subject to a string-validity check. Same recurrence shape, decorated.
• Tribonacci. $f(n) = f(n-1) + f(n-2) + f(n-3)$. Three-variable collapse instead of two; matrix exponentiation generalizes naturally.
• Domino tilings. Surprisingly often reduce to Fibonacci-like recurrences; the matrix-exponentiation trick handles huge boards.

The reflex: when a recurrence depends on a constant number of previous values, the DP can always be done in that number of variables — and matrix exponentiation gives a $O(\log n)$ option if the input ranges demand it.

What to say out loud — the delivery script

Ten beats:

1. “Let me restate: count the distinct ordered sequences of 1-step and 2-step hops that climb $n$ stairs.”
2. Ask: “upper bound on $n$? hops just 1 and 2? does order matter?”
3. “The recurrence: to reach stair $n$, the last hop was either a 1 or a 2, so $f(n) = f(n-1) + f(n-2)$ with $f(0) = f(1) = 1$. That’s Fibonacci.”
4. “Naive recursion is $O(2^n)$ — same subproblems get computed many times. Let me name that and move on.”
5. “Memoization caches each $f(k)$ on first computation: $O(n)$ time, $O(n)$ space.”
6. “Bottom-up makes the iteration order explicit: fill from $i = 2$ to $n$. The key observation is that we only ever need the last two values, so the array collapses to two variables — $O(1)$ space.”
7. Write the bottom-up code — six lines. Trace $n = 5$: 1, 1, 2, 3, 5, 8.
8. “Edge cases: $f(0)$ and $f(1)$ both return 1 directly; the loop just doesn’t execute. For large $n$, switch to long long to avoid overflow.”
9. “For the senior bonus: matrix exponentiation gives $O(\log n)$. The Fibonacci matrix raised to $n$ encodes $f(n+1)$ and $f(n)$ in its first row. Useful when $n$ is huge.”
10. “For the standard interview, I’d ship the two-variable bottom-up. If the interviewer pushes on huge $n$, I’d offer the matrix version.”

Summary

Climbing Stairs is the rite of passage for dynamic programming. The interview signal isn’t producing the optimal answer — it’s articulating the recurrence in one sentence, then walking the four-step optimization staircase: naive → memoized → bottom-up → matrix exponentiation. Each step teaches a different DP move, and every later DP problem reuses one or more of them.

The wider lesson is the constant-state recognition. Many DP problems have recurrences that depend on a fixed-size window of previous values — Fibonacci, House Robber, Kadane’s, decode-ways, tilings — and every one of them collapses to a fixed-size set of running variables. Internalize that shape here; the rest of the easier DP family becomes pattern matching.