Story Hook: “Compute the 400th Fibonacci term… using simple recursion.”
Naive recursion looks short and innocent — but the recursion tree explodes.
Estimated calls ≈ 1083
Time @ 1 ns/call ≈ 1067 years
Earth’s age is only ~ 4.5 × 109 years.
🦕 Started at Earth’s birth… still running today 😄
🦕 Started in dinosaur age…
🌍 Still not finished…
⏳ DP saves the day.
See the approximation (simple + realistic)
🔁 Naive Fibonacci recursion makes roughly:
≈ 1083 function calls
⚡ If each call takes 1 nanosecond (10-9 sec):
Total time ≈ 1067 years
🌍 Earth’s age ≈ 4.5 × 109 years
🦕 If it started at Earth's birth… it would still be running today 😄
🦕 If it started at Earth's birth… it would still be running today 😄
Key idea: same subproblems repeat 🔁
DP caches results ✅
Time drops to O(n) for Fibonacci ⚡
Still computing F(400)… ETA: ∞
1) Overlapping Subproblems
Same subproblems appear again and again. Store once → reuse.
Cache / memo table
“Solve once”
2) Optimal Substructure
Optimal answer can be built from optimal answers of smaller subproblems.
Build small → big
Reuse best sub-answers
Two DP Styles
Top-Down (Memoization)
Recursion + memo[]; avoids recomputation using memo hits.
Recursion + cacheMay hit recursion depth
Bottom-Up (Tabulation)
Iteratively fill dp[] from base cases to answer.
Loop + tableEasy space optimization
Interactive Demo: Fibonacci with DP
Switch modes, then Step/Auto to watch memo/dp fill.
Demo n:
(≤ 40 for smooth steps)
Computed states
0
Memo hits (Top-Down)
0
Total calls
0
Result fib(n)
—
🧠 Debug View (Pseudocode + Step Meaning + Call Stack + Mini Tree)
Pseudocode (auto-switches)
What this step means
Click Step to start. “MEMO HIT” means subtree skipped ✅
Call Stack (Top-Down)
Top of stack ↓
(empty)
Push on CALL, pop on RETURN.
Why it helps
Shows which calls are waiting. MEMO HIT returns immediately without growing the stack.
🌳 Mini Recursion Tree (Top-Down)
Tree view limited to n ≤ 8 for clarity.
(tree will appear here)
Tip: Click Run, then use Step or Auto.
DP / Memo Table
index → value
What to notice
Top-Down: memo hit → instant return (skips subtree).
Bottom-Up: dp[0..n] filled once in order.
Bottom-Up: dp[0..n] filled once in order.
Next in DP Module
Continue module-wise from your index placeholders: