Understand
30-second explanation
Build the interview-ready mental model before comparing implementations.
The number of ways to reach step n is ways(n-1) + ways(n-2) — it's Fibonacci in disguise. Naive recursion is O(2ⁿ); memoize to O(n), then collapse the array to two rolling variables for O(n) time and O(1) space.
Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview contextHide interview context
What's being tested
Whether you can derive a recurrence from the problem structure, recognize the overlapping subproblems, and progress from exponential recursion to a linear DP — narrating each speed-up.
Where candidates slip
Jumping straight to the formula without explaining WHY f(n) = f(n-1) + f(n-2), or shipping the naive recursion that times out for n = 45.
How to stand out
Name it as Fibonacci, derive the recurrence from 'the last move is 1 or 2 steps', then optimize space to O(1) and mention matrix exponentiation as the O(log n) flex.
Choose
Compare the available approaches
Use constraints and trade-offs to select the route you can defend in an interview.
Interactive decision treeInteractiveChoose the right approachFirst decision previewCount ways to reach step n by 1 or 2 stepsBrute force the recursion tree?YesNoExplore the full treeCollapse the tree
Learn & trace
Build each solution step by step
Move from the core idea to a visual trace, implementation, proof, and edge cases.
Approach 1 of 3
Brute Force — Plain Recursion
1Hint 1Explore hintHide hint
Think about the very last move you make to land on step n. How many options are there, and where could you have been just before?
2Hint 2Explore hintHide hint
If your last move was a single step you were on n-1; if it was a double step you were on n-2. The ways to reach n is the sum of the ways to reach those two stairs.
3Hint 3Explore hintHide hint
Write f(n) = f(n-1) + f(n-2) with f(0) = 1 and f(1) = 1, recursing straight down.
A · Core idea
Translate the problem directly into a recurrence by reasoning about the last move. To stand on step n, your final hop was either a single step (so you were on n-1) or a double step (so you were on n-2). Those are the only two ways to arrive, and they're mutually exclusive, so the total count is f(n-1) + f(n-2).
The mental shift that unlocks every DP problem. Don't think about the first move and all the branching futures — think about the last move and where it could have come from. That single reframe turns an intimidating 'count all paths' question into a two-term sum. The base cases fall out naturally: there's exactly one way to be standing on step 0 (do nothing) and one way to reach step 1 (a single step).
Why this recurrence is literally Fibonacci. f(n) = f(n-1) + f(n-2) with f(0) = f(1) = 1 is the Fibonacci sequence shifted by one index. Recognizing that out loud signals maturity — and hints at the O(log n) matrix-exponentiation trick for the follow-up.
Why we don't ship this. The recursion tree recomputes f(n-2) twice, f(n-3) three times, and so on — exponential blowup. For n = 45 that's ~3.5 billion calls and a guaranteed TLE. State this cost, then fix it with a cache.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
n = 4f(4)
= f(3) + f(2)
expand f(3) first5C · Code with teaching comments
Reference implementation previewpublic int climbStairs(int n) { if (n <= 1) { return 1; } return climbStairs(n - 1) + climbStairs(n - 2);Explore the full codeHide the full code
D · Why it works and complexityO(2ⁿ) timeO(n) spaceOpen the invariant and proofExplore the proofHide the proof
The killer observation is that the recursion tree is full of repeated subproblems — f(3) gets computed over and over from different branches. Whenever a recurrence's call tree overlaps like that, caching collapses exponential work into linear. That single realization is the gateway from recursion to dynamic programming.
ComplexityO(2ⁿ) time, O(n) space — Each call spawns two more, forming a binary recursion tree of depth n → about 2ⁿ nodes. The recursion stack adds O(n) space.
E · Edge cases and pitfalls4n = 1 — Hits the base guard immediately and returns 1 — the only way is a single step.Explore edge casesHide edge cases
Edge cases handled
n = 1Hits the base guard immediately and returns 1 — the only way is a single step.
Pitfalls
- Returning 0 for the base case instead of 1 — collapses every value above to 0.
- Using max(...) instead of + — confuses this counting problem with an optimization one like House Robber.
- Shipping this as the final answer — it TLEs around n = 40 and signals you didn't see the overlap.
Approach 2 of 3
Top-Down Memoization
1Hint 1Explore hintHide hint
Every f(i) has one fixed value. What if you computed each one only the first time and reused it afterward?
2Hint 2Explore hintHide hint
Keep an array (or map) memo[] where memo[i] caches f(i). Before recursing, check whether it's already filled.
3Hint 3Explore hintHide hint
Fill memo[i] = solve(i-1) + solve(i-2) once; on later calls return the stored value in O(1).
A · Core idea
Keep the exact same recurrence, but remember each answer the first time you compute it. A memo array (indexed by step) starts empty; solve(i) checks the cache, and only on a miss does it recurse into solve(i-1) + solve(i-2) and store the result.
The mental shift: trade memory for repeated work. The brute force was slow purely because it re-derived the same f(i) from scratch every time it appeared in the tree. By writing each answer down the first time, every subsequent occurrence becomes a free lookup. The shape of the code barely changes — you add a cache check at the top and a cache write before the return — but the complexity drops from exponential to linear.
Why memoization is 'top-down'. We still start the question at n and recurse down toward the base cases, exactly mirroring how you'd reason about it on a whiteboard. That makes it the gentlest leap from a working recursive solution: you don't have to figure out the right iteration order, the recursion discovers it for you.
Why the cache check must come first. The very first line of solve returns the cached value if present. Skip that guard and you'd still recurse on every call — defeating the entire optimization and silently dropping you back to O(2ⁿ).
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
n = 4solve(4)
miss → needs solve(3) + solve(2)
memo = {}5C · Code with teaching comments
Reference implementation previewpublic int climbStairs(int n) { int[] memo = new int[n + 1]; Arrays.fill(memo, -1); return solve(n, memo); }Explore the full codeHide the full code
D · Why it works and complexityO(n) timeO(n) spaceOpen the invariant and proofExplore the proofHide the proof
Memoization is the universal 'first DP' move: take any correct-but-slow recursion with overlapping subproblems, bolt on a cache, and you get the optimal time complexity essentially for free. The art of DP that follows — bottom-up tabulation, space compression — is just refining what memoization already proves correct.
ComplexityO(n) time, O(n) space — Each of the n distinct subproblems is solved exactly once and then cached; every later request is an O(1) array read. n subproblems × O(1) work = O(n) time, plus O(n) for the memo array and recursion stack.
E · Edge cases and pitfalls5n = 1 — Base guard fires before the cache is touched, returning 1 without recursion.Explore edge casesHide edge cases
Edge cases handled
n = 1Base guard fires before the cache is touched, returning 1 without recursion.n = 45Only 45 distinct subproblems are ever computed, so it finishes instantly where the plain recursion would TLE.
Pitfalls
- Forgetting to write to memo before returning — you'd recurse every time and stay exponential.
- Using 0 as the 'uncomputed' sentinel — but 0 is never a real answer here so it happens to work; -1 is safer as a habit.
- Putting the cache check after the recursive call instead of before it — does nothing for performance.
Approach 3 of 3 · Optimal
Bottom-Up — Two Rolling Variables (Optimal)
1Hint 1Explore hintHide hint
If you build the answers from the bottom (f(2), then f(3), ...) instead of the top, what's the minimum state you need to compute the next value?
2Hint 2Explore hintHide hint
Each f(i) depends only on the two values immediately before it. So you never need the full array — just the previous two numbers.
3Hint 3Explore hintHide hint
Keep prev2 and prev1, loop from 2 to n, set cur = prev1 + prev2, then slide the window: prev2 = prev1, prev1 = cur.
A · Core idea
Flip the direction: instead of recursing down from n, build up from the base cases. Start with the answers for steps 0 and 1 (both 1), then iterate forward computing each cur = prev1 + prev2 and sliding the two-element window forward.
The mental shift: you don't need history you'll never read again. The recurrence only ever reaches back two indices. So while a full dp[] array works, almost all of it is dead weight — once dp[i] is computed, dp[i-2] and everything older is never touched again. Keeping just the trailing two values gives the identical answer with constant memory. This 'rolling variables' compression is the signature move on every linear-recurrence DP.
Why bottom-up removes the recursion entirely. Going forward from the base cases means each value's dependencies are already computed by the time we need them — no call stack, no memo lookups, no risk of stack overflow on large n. It's the same computation the memoized version does, just in an explicit, cache-friendly loop.
Why the assignment order matters. Inside the loop you must compute cur before overwriting prev1. Update prev2 = prev1 and prev1 = cur in that order — flip them and you'd clobber prev1 before reading it, corrupting every value downstream. This line-ordering trap is the constant-space equivalent of Two Sum's check-before-insert.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
n = 5Array state
init
f(0)=1, f(1)=1 seeded
8C · Code with teaching comments
D · Why it works and complexityO(n) timeO(1) spaceOpen the invariant and proofExplore the proofHide the proof
Space compression is the final polish on most 1D DPs: ask 'how far back does my recurrence actually reach?' If the answer is a small constant k, you only need k rolling variables, not an O(n) array. Climbing Stairs reaches back 2, so 2 variables suffice — the same trick shrinks Fibonacci, House Robber, and Min Cost Climbing Stairs to O(1) space.
ComplexityO(n) time, O(1) space — A single loop from 2 to n does O(1) arithmetic per iteration → O(n) time. We store only two integers regardless of n → O(1) space.
E · Edge cases and pitfalls5n = 1 — The guard returns 1 before the loop runs — there's no i = 2 iteration to perform.Explore edge casesHide edge cases
Edge cases handled
n = 1The guard returns 1 before the loop runs — there's no i = 2 iteration to perform.n = 2One loop iteration: cur = 1 + 1 = 2, returns 2. Smallest case that exercises the loop.
Pitfalls
- Writing prev1 = cur before prev2 = prev1 in the Java version — clobbers prev1 and corrupts the sequence.
- Forgetting the n ≤ 1 guard — the loop never runs but prev1 is still 1, so it happens to be correct here; keep the guard for clarity.
- Returning prev2 instead of prev1 at the end — off-by-one that returns f(n-1).
Practice
Try the solution yourself
Edit the optimal implementation, test another input, and observe the result.
Editable code previewpublic int climbStairs(int n) { if (n <= 1) { return 1; } int prev2 = 1, prev1 = 1;Explore the playgroundClose the playground
Avoid mistakes
Recognize the interview traps
Understand why common attempts fail before reviewing the corrected implementation.
1Summing vs. maximizing
Climbing Stairs COUNTS distinct paths, so the two predecessors must be added. Using max turns it into an unrelated optimization problem and returns 1 for every n.
Explore the code comparisonHide the code comparison
Summing vs. maximizing
Climbing Stairs COUNTS distinct paths, so the two predecessors must be added. Using max turns it into an unrelated optimization problem and returns 1 for every n.
Don't write this
int cur = Math.max(prev1, prev2);Write this instead
int cur = prev1 + prev2;2Wrong base case value
f(0) and f(1) must both be 1. Returning 0 for the base case makes every recursive value collapse to 0.
Explore the code comparisonHide the code comparison
Wrong base case value
f(0) and f(1) must both be 1. Returning 0 for the base case makes every recursive value collapse to 0.
Don't write this
if n <= 1:
return 0Write this instead
if n <= 1:
return 13Clobbering prev1 before reading it
In the rolling-variable loop, updating prev1 before prev2 overwrites the value prev2 still needs, corrupting every later term.
Explore the code comparisonHide the code comparison
Clobbering prev1 before reading it
In the rolling-variable loop, updating prev1 before prev2 overwrites the value prev2 still needs, corrupting every later term.
Don't write this
prev1 = prev1 + prev2;
prev2 = prev1;Write this instead
int cur = prev1 + prev2;
prev2 = prev1;
prev1 = cur;Revise
Carry the pattern into the interview
Pattern to remember
1D bottom-up DP (Fibonacci recurrence)
Code pattern to memorize
dp[i] = dp[i-1] + dp[i-2]
base: dp[0] = 1, dp[1] = 1
# O(1) space: keep only prev2, prev1 and roll them forwardRules to remember
- 1The recurrence is
f(n) = f(n-1) + f(n-2)— the LAST move is either a 1-step or a 2-step, so total ways = ways into n-1 + ways into n-2. - 2Base cases are
f(0) = 1(one way to stand still) andf(1) = 1— get these wrong and every value above is off. - 3Naive recursion recomputes the same subproblems exponentially — add memoization or go bottom-up, never ship the plain recursion.
- 4You only ever read the previous two values, so drop the array and keep two variables — O(1) space.
- 5Sum the two ways, don't
maxthem. This is a counting problem, not an optimization problem — a classic mix-up with House Robber.
Use this pattern when
- Counting the number of distinct ways to reach a target by fixed step sizes
- Each state depends only on a small fixed number of previous states
- The brute-force recursion tree shows overlapping subproblems
- Answer for n is built cleanly from answers for n-1 and n-2
Choose another pattern when
- You need the actual paths, not the count → backtracking, not DP counting
- Step sizes are unbounded or variable per stair → graph BFS / different DP
- You're maximizing/minimizing a value, not counting → still DP but with max/min, not sum
- n is astronomically large and you need it mod p fast → matrix exponentiation O(log n)
Interview takeaway
Climbing Stairs is the 'hello world' of dynamic programming: spot the overlapping-subproblem recurrence, memoize it, then realize you only need O(1) state. Once you see this shape you'll recognize it in House Robber, Decode Ways, Min Cost Climbing Stairs, and Fibonacci itself — one recurrence, many costumes.
Continue
Transfer the pattern to another problem
Use a direct variation or pattern sibling to prove the idea is reusable.
Transferable patternCanonical 1D Dynamic Programming on a linear recurrence. Recognize it whenever each state depends on a small fixed number of earlier states. Same shape as Fibonacci, Min Cost Climbing Stairs, Decode Ways, and House Robber.
Practice queueDirect variations and pattern siblings
Direct follow-ups
- Min Cost Climbing StairsComing soonSame two-step recurrence, but now minimize accumulated cost: dp[i] = cost[i] + min(dp[i-1], dp[i-2]).
- Fibonacci NumberComing soonLiterally the same recurrence with f(0)=0, f(1)=1 — the bare skeleton of this problem.
- Decode WaysCounting paths with two-step look-back again, but transitions are conditional on valid 1- and 2-digit codes.
- House RobberSame dp[i-1] vs dp[i-2] shape, but you MAX over 'skip' vs 'take', not sum.