How Do You Solve Fibonacci with Dynamic Programming?
Learn how dynamic programming speeds up Fibonacci from O(2^n) to O(n), with memoization and O(1)-space tabulation code.
Expected Interview Answer
Naive recursive Fibonacci recomputes the same subproblems exponentially many times, costing O(2^n) time, so dynamic programming fixes this by storing each F(i) the first time it is computed and reusing it, bringing the cost down to O(n) time with either O(n) space (tabulation) or O(1) space (two rolling variables).
The recurrence F(n) = F(n-1) + F(n-2) with base cases F(0)=0, F(1)=1 has massive overlapping subproblems: the naive recursion tree for F(n) calls F(n-2) twice, F(n-3) three times, and so on, an exponential blowup captured by the recursion's own Fibonacci-shaped branching. Top-down memoization caches each F(i) in a dictionary or array the first time it's computed, so every subsequent call short-circuits to O(1); this preserves the natural recursive structure while fixing the complexity. Bottom-up tabulation instead builds F(0), F(1), ..., F(n) in a simple loop, and because only the previous two values are ever needed, the array can be collapsed to two rolling variables for O(1) space. Both approaches are O(n) time; there is also a O(log n) matrix-exponentiation method for very large n, but tabulation is what interviewers expect as the standard answer.
- Reduces exponential O(2^n) naive recursion to linear O(n) time
- Bottom-up tabulation needs only O(1) space with two rolling variables
- Top-down memoization preserves natural recursive structure while fixing complexity
- Demonstrates the overlapping-subproblems + optimal-substructure DP signature cleanly
AI Mentor Explanation
A scorer computing a player's projected milestone total the naive way keeps re-deriving the same earlier innings totals over and over, since each projection recursively depends on the two previous innings' projections, and those in turn depend on the two before them, exploding into a tree of repeated recalculations. Instead, the scorer writes down each innings' projection the first time it's worked out, in a simple running ledger from the first innings up to the current one. Because each new projection only ever needs the previous two entries, the scorer doesn't even need the full ledger — just the last two numbers carried forward. This turns a recalculation-heavy exponential process into one quick pass through the innings list.
Step-by-Step Explanation
Step 1
Identify overlapping subproblems
Naive recursion F(n)=F(n-1)+F(n-2) recomputes the same F(i) exponentially many times.
Step 2
Choose memoization or tabulation
Top-down: cache each F(i) in a dict/array on first computation. Bottom-up: build F(0)..F(n) in a loop.
Step 3
Apply the base cases
F(0) = 0, F(1) = 1 anchor the recurrence for both approaches.
Step 4
Optimize space
Since only the previous two values are ever needed, collapse the array to two rolling variables for O(1) space.
What Interviewer Expects
- Identify overlapping subproblems as the reason naive recursion is O(2^n)
- Implement either top-down memoization or bottom-up tabulation correctly
- Recognize the O(1) space optimization using two rolling variables
- Mention (as a bonus) the O(log n) matrix exponentiation approach exists for very large n
Common Mistakes
- Writing naive recursion and calling it “solved” without adding memoization
- Off-by-one errors in the base cases or loop bounds
- Using a full O(n) array when O(1) rolling variables would suffice and is expected as a follow-up
- Confusing memoization (top-down, cache-as-you-go) with tabulation (bottom-up, build-in-order)
Best Answer (HR Friendly)
“The naive way to compute Fibonacci numbers recursively ends up solving the same smaller problems over and over, which gets exponentially slow. I fix that with dynamic programming by either remembering each answer the first time I compute it, or by building up the answers in order from the smallest to the largest, which brings it down to linear time and can even be done with just two variables instead of a whole array.”
Code Example
def fib_memo(n, cache=None):
if cache is None:
cache = {}
if n in (0, 1):
return n
if n in cache:
return cache[n]
cache[n] = fib_memo(n - 1, cache) + fib_memo(n - 2, cache)
return cache[n]
def fib_tabulation_o1_space(n):
if n in (0, 1):
return n
prev, curr = 0, 1
for _ in range(2, n + 1):
prev, curr = curr, prev + curr
return curr
print(fib_memo(30)) # 832040
print(fib_tabulation_o1_space(30)) # 832040Follow-up Questions
- How would you compute Fibonacci numbers in O(log n) using matrix exponentiation?
- What is the space complexity difference between memoization and the O(1) rolling-variable approach?
- How would you handle Fibonacci for very large n where results overflow standard integer types?
- How does this same overlapping-subproblems pattern show up in other DP problems like climbing stairs?
MCQ Practice
1. What is the time complexity of naive recursive Fibonacci without memoization?
Without memoization, the recursion tree branches into two calls at every level, giving exponential O(2^n) time.
2. What is the minimum space complexity achievable for computing F(n) with dynamic programming?
Since only the previous two Fibonacci values are ever needed, two rolling variables suffice, giving O(1) space.
3. What are the standard base cases for the Fibonacci recurrence?
The conventional Fibonacci sequence starts with F(0)=0 and F(1)=1, anchoring the F(n)=F(n-1)+F(n-2) recurrence.
Flash Cards
Why is naive recursive Fibonacci slow? — It has overlapping subproblems that get recomputed exponentially many times, giving O(2^n) time.
What is the time complexity of DP Fibonacci? — O(n), whether using top-down memoization or bottom-up tabulation.
What is the minimum space complexity for DP Fibonacci? — O(1), by keeping only the previous two values in rolling variables.
What technique computes Fibonacci in O(log n)? — Matrix exponentiation, using fast exponentiation of the [[1,1],[1,0]] matrix.