Climbing stairs: the DP that is Fibonacci

Interview QuestionsBy Ashish JangraUpdated 15 September 2026

ways(n) = ways(n-1) + ways(n-2), because the last move was either one step or two. That is Fibonacci. Written as plain recursion it is exponential; the same recurrence computed once per value is O(n), and since only the last two values are ever needed it is O(1) space.

Overview

The question, and what it is testing

Dynamic programmingCoding problemEasy

Step through it

What to watch

The call count roughly doubles per extra step — that is the overlap, measured.
Filling forwards computes each value exactly once.
Only the last two entries are ever read, which is why the table can go.

Say this out loud

"The last move was either a single step from n-1 or a double from n-2, so ways(n) = ways(n-1) + ways(n-2) with ways(1) = 1 and ways(2) = 2. It is Fibonacci. Naive recursion is exponential because the subproblems overlap, so I either memoise or fill a table forwards - and since only the last two entries are read, two variables are enough. O(n) time, O(1) space."

import functools, sys calls = 0 def naive(n): """Correct, and exponential: the subproblems overlap.""" global calls calls += 1 if n <= 2: return n return naive(n - 1) + naive(n - 2) print("plain recursion:") for n in (10, 20, 25): calls = 0 v = naive(n) print(f" ways({n:>2}) = {v:>7,} calls: {calls:>9,}") print(" the call count grows exponentially, not linearly") @functools.lru_cache(maxsize=None) def memo(n): """Top-down: same recurrence, each value computed once.""" if n <= 2: return n return memo(n - 1) + memo(n - 2) def table(n): """Bottom-up: no recursion, so no stack limit.""" if n <= 2: return n best = [0] * (n + 1) best[1], best[2] = 1, 2 for i in range(3, n + 1): best[i] = best[i - 1] + best[i - 2] return best[n] def rolling(n): """Only the last two entries are ever read.""" if n <= 2: return n a, b = 1, 2 for _ in range(n - 2): a, b = b, a + b return b

import functools, sys calls = 0 def naive(n): global calls calls += 1 if n <= 2: return n return naive(n - 1) + naive(n - 2) @functools.lru_cache(maxsize=None) def memo(n): if n <= 2: return n return memo(n - 1) + memo(n - 2) def table(n): if n <= 2: return n best = [0] * (n + 1) best[1], best[2] = 1, 2 for i in range(3, n + 1): best[i] = best[i - 1] + best[i - 2] return best[n] def rolling(n): if n <= 2: return n a, b = 1, 2 for _ in range(n - 2): a, b = b, a + b return b n = 30 print() print(f"ways({n}):") print(f" memoised {memo(n):>8,} cache holds {memo.cache_info().currsize} entries") print(f" table {table(n):>8,} list of {n + 1} ints") print(f" rolling {rolling(n):>8,} 2 variables") print(" all agree:", memo(n) == table(n) == rolling(n)) print(" and they agree with the naive version at n=25:", naive(25) == rolling(25)) print() print("it is Fibonacci:") print(" ways(1..10) =", [rolling(i) for i in range(1, 11)])

import functools, sys calls = 0 def naive(n): global calls calls += 1 if n <= 2: return n return naive(n - 1) + naive(n - 2) @functools.lru_cache(maxsize=None) def memo(n): if n <= 2: return n return memo(n - 1) + memo(n - 2) def table(n): if n <= 2: return n best = [0] * (n + 1) best[1], best[2] = 1, 2 for i in range(3, n + 1): best[i] = best[i - 1] + best[i - 2] return best[n] def rolling(n): if n <= 2: return n a, b = 1, 2 for _ in range(n - 2): a, b = b, a + b return b # The reason to prefer bottom-up when n is large. print() print("recursion limit:", sys.getrecursionlimit()) try: memo.cache_clear() memo(4_000) except RecursionError as e: print(" memo(4000) -> RecursionError:", str(e)[:40]) print(" rolling(4000) has", len(str(rolling(4_000))), "digits and no stack cost")

Climbing stairs: the DP that is Fibonacci

ways(n) = ways(n-1) + ways(n-2), because the last move was either one step or two. That is Fibonacci. Written as plain recursion it is exponential; the same recurrence computed once per value is O(n), and since only the last two values are ever needed it is O(1) space.

INTERVIEW · vizlearn.in/interview/climbing-stairs.html

About the author

Ashish Jangra builds and maintains VizLearn. Every module here is written and the visualisation behind it hand-built, so the numbers in a readout come from the same code that draws the picture. Corrections are genuinely welcome and get priority over everything else — if a page states something wrong, or an animation misrepresents what the algorithm does, get in touch.

Climbing stairs: the DP that is Fibonacci

Overview

The question, and what it is testing

Step through it

What to watch

Say this out loud