Climbing Stairs
You can climb one or two steps at a time — how many distinct ways are there to reach step n? The recurrence falls out of a single observation about the last move you made, and the resulting solution needs no array at all once you notice that each answer depends on only the two before it.
This isn't a canned animation. DryRun compiles and executes the code below, then draws every step from the real trace — the same values your machine would produce.
The code
int climbStairs(int n) {
if (n <= 2) return n;
int prev2 = 1;
int prev1 = 2;
for (int i = 3; i <= n; i++) {
int cur = prev1 + prev2;
prev2 = prev1;
prev1 = cur;
}
return prev1;
}
int main() {
for (int n = 1; n <= 8; n++) {
cout << climbStairs(n) << ' ';
}
return 0;
}Rolling two variables instead of an n-element table; the printed sequence 1 2 3 5 8 13 21 34 is Fibonacci shifted by one.
How it works, step by step
Reason about the last step, not the first
Any route to step n ends with either a 1-step or a 2-step move. Those two cases are disjoint and cover everything, so ways(n) = ways(n-1) + ways(n-2). Framing the recurrence by the final decision is a habit that generalises to most counting DP problems.
The base cases are counts, not indices
There is exactly 1 way to reach step 1 and 2 ways to reach step 2 (1+1 or 2). Getting these wrong shifts the entire sequence, and since the shifted sequence is still Fibonacci it still looks plausible.
Bottom-up means no recursion at all
Because state i depends only on smaller states, a simple ascending loop fills them in dependency order. There is no call stack, so this version cannot overflow no matter how large n gets.
Two variables replace the table
The recurrence reaches back exactly two positions, so nothing older than that is ever needed again. prev1 and prev2 slide forward each iteration, cutting memory from O(n) to O(1) without changing a single result.
The assignment order matters
cur must be computed before prev2 is overwritten, and prev2 must take the old prev1 before prev1 is updated. Reorder those three lines and the sequence silently becomes powers of two.
Complexity
One addition per step with no table at all; the naive recursive formulation of the same recurrence is exponential for exactly the reason naive Fibonacci is, since it recomputes overlapping subproblems instead of reusing them.
Common bugs
Off-by-one base cases
Returning 1 for n = 2 instead of 2 shifts the whole sequence down by one, and because the result is still a Fibonacci number the output looks reasonable. Verify by hand: two steps can be climbed as 1+1 or as 2, so the answer is 2.
Updating prev1 before prev2
Writing prev1 = cur; prev2 = prev1; makes prev2 take the new value rather than the old one, so both variables end up equal and the sequence becomes 1, 2, 4, 8. Watching the two variables after each iteration makes the doubling obvious within two steps.
Solving it recursively without memoization
The naive recursion is a one-liner and takes exponential time, so n = 45 hangs. If your solution is correct on small inputs and times out on large ones, this is almost always why. Either memoize or use the loop.
Integer overflow past n = 46
The count grows like Fibonacci, exceeding the range of a 32-bit int at around n = 46 and wrapping to a negative number. Use long long if n can be large, and note that no amount of DP correctness saves you from an overflowing accumulator.
Each of these is easier to see than to describe — step through it and watch the values change. Run it in DryRun.
Frequently asked
Why is climbing stairs the same as Fibonacci?
Because both satisfy the recurrence f(n) = f(n-1) + f(n-2). Every route to step n ends with a move of either 1 or 2 steps, so the total splits into routes to step n-1 and routes to step n-2. The only difference from standard Fibonacci is the starting values, which shift the sequence by one position.
How do you solve climbing stairs in O(1) space?
Keep only the last two counts in two integer variables and slide them forward on each iteration. The recurrence never looks back further than two positions, so the rest of the DP table is dead weight. Update the older variable from the newer one before overwriting the newer one.
What is the difference between top-down and bottom-up here?
Top-down writes the recursion with a memo table and computes states on demand, using O(n) stack depth. Bottom-up starts at the base cases and loops upward, using no stack at all. For this problem bottom-up is strictly better — the dependency order is trivially known, so there is nothing to gain from recursion.
What if you can climb 1, 2 or 3 steps at a time?
The recurrence becomes f(n) = f(n-1) + f(n-2) + f(n-3), producing the tribonacci sequence, and you carry three rolling variables instead of two. The same reasoning extends to any fixed set of allowed step sizes: sum the counts for each possible last move.