A facilities spec for a new mezzanine: each stride is one riser or two. Compliance wants the count of distinct sequences to the top, not a drawn path. The intern recursed from step n: last hop was 1, or last hop was 2. A six-step stub returned. A forty-step atrium was still expanding the tree when the inspection window closed.

Climbing Stairs asks how many 1-or-2 sequences sum to n. An array of landings already gives each step for free. Recursing every last-hop fork uses that picture and still pays an exponential tree. The last landing is either a 1 from n-1 or a 2 from n-2.

This is an interview writeup, not a Fibonacci lecture. You only need the two previous counts.

The problem

Given an int n, a staircase has n steps. Each move takes either 1 step or 2 steps. Return how many distinct sequences of 1s and 2s sum to n. Order matters: 1 then 2 is not 2 then 1.

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

Note: Sequences, not combinations. 1+2 and 2+1 are two ways. You cannot skip a riser or take three at once. n = 0 is usually off the prompt; if they ask, the empty sequence is one way.

Recursing last hop 1 or 2 is the honest brute force

From remaining height left, take 1 and recurse, or take 2 and recurse. Hitting 0 is one way. Going negative is zero. Correct. Exponential: each call forks twice, and the same remaining height is expanded over and over.

int climbRec(int n) {
    return from(n);
}

int from(int left) {
    if (left == 0) {
        return 1;
    }
    if (left < 0) {
        return 0;
    }
    return from(left - 1) + from(left - 2);
}

At n = 8 this is a rounding error. At a tall atrium you paid a search tree for a question two rolling counts answer: ways to n = ways to n-1 plus ways to n-2? Memoizing from(left) is the same recurrence filled on demand. Still not a reason to keep the tree at the board.

Two integers: last landing was one, or two

Let prev2 be ways to reach the step two behind, prev1 the step one behind. Seed prev2 = 1 (ways to height 0 — do nothing) and prev1 = 1 (one single step to height 1). For each height 2 .. n, the new count is prev1 + prev2, then shift.

You never fork. You never store n cells unless they ask for the table.

n = 4
height 0:  1
height 1:  1     (1)
height 2:  2     (1+1), (2)
height 3:  3     from 2 by +1, or from 1 by +2
height 4:  5     from 3 by +1, or from 2 by +2

The Java is that shift:

int climbStairs(int n) {
    int prev2 = 1;
    int prev1 = 1;
    for (int i = 2; i <= n; i++) {
        int cur = prev1 + prev2;
        prev2 = prev1;
        prev1 = cur;
    }
    return prev1;
}

Time is O(n) — one pass, constant work per height. Space is O(1) — two rolling integers. An int[] of size n + 1 is the same recurrence with extra cells you do not read except i-1 and i-2.

Note: n = 1 must return 1. The loop does not run; prev1 stays the seed. Do not special-case n = 2 as if it were a different problem — it is 1 + 1. Adding the two branches as combinations (n/2 + 1) undercounts because order matters.

What interviewers usually poke next

  • The int[] table. dp[0] = dp[1] = 1, then dp[i] = dp[i-1] + dp[i-2]. Same numbers. Say you would roll it unless they want the array.
  • Memo DFS. Cache from(left). O(n) time after the first fill, O(n) stack plus map. Name it, then go back to the two integers.
  • Overflow. Counts grow like Fibonacci. Interview n often fits in int; a taller stair needs long. Ask.
  • k-step hops. Last hop in 1..k. Then you need the last k counts, not two. Do not stretch this loop.
  • Decode Ways. Same sibling shape — land from one back or two back — except each hop is gated by digits. Different prompt. Do not switch.

You are done with this problem when you can walk n = 4 to 5 on a whiteboard with two rolling integers, and you can say out loud why the last-hop tree is correct and why you do not expand it.