1. One-Liner
Fibonacci DP stores previously computed F(i) values so each index is evaluated once, turning exponential recursion into linear work.
2. The Problem It Solves
Naive recursion for F(n) = F(n-1) + F(n-2) recomputes the same subproblems many times. You need the same mathematical sequence but with efficient time and predictable stack usage (tabulation) or top-down caching (memoization).
3. The Core Idea
Each F(k) depends only on shorter prefixes. Once F(k) is known, reuse it everywhere it is needed—like writing answers on a chalkboard instead of redoing the full derivation each time.
4. How It Works (Step-by-Step)
| Step | What Happens |
|---|---|
| 1. Base | Set F(0)=0, F(1)=1 (or your problem’s definition) |
| 2. Order | For i from 2 to n, compute F(i)=F(i-1)+F(i-2) |
| 3. Storage | Keep an array dp[i] or two rolling variables |
| 4. Answer | Return dp[n] |
5. Dry Run Example
n=5: dp=[0,1] → i=2:1 → i=3:2 → i=4:3 → i=5:5. Result 5.
6. Key Properties
| Property | Value |
|---|---|
| Optimal substructure | Yes |
| Overlapping subproblems | Yes (classic) |
| State | Single index i |
7. Where It Is Used
| Domain | Use |
|---|---|
| Interviews | Canonical DP introduction |
| Algorithms | Prototype for linear DP and rolling array optimization |
8. Interview Tips
Mention memo vs tabulation, O(n) time / O(1) space with two variables, and matrix exponentiation for O(log n) if asked for huge n.
9. Comparison with Other Approaches
| Approach | Time | Space | Notes |
|---|---|---|---|
| Naive recursion | Exponential | O(n) stack | Recomputes |
| DP array | O(n) | O(n) | Simple |
| Two variables | O(n) | O(1) | Rolling |
10. Complexity
| Metric | Value |
|---|---|
| Time | O(n) with array; O(1) per step with rolling vars |
| Space | O(n) or O(1) extra |
Implementation Example (PYTHON)
def fibonacci(n: int) -> int:
if n <= 1:
return n
a, b = 0, 1
for _ in range(2, n + 1):
a, b = b, a + b
return b