Fibonacci Sequence with DP
What you'll learn: How to transform the classic Fibonacci problem from exponentially slow to lightning-fast using memoization and tabulation.
The Problem
The Fibonacci sequence (0, 1, 1, 2, 3, 5, 8...) is defined as: F(n) = F(n-1) + F(n-2), with F(0) = 0 and F(1) = 1. The naive recursive solution recalculates the same values thousands of times—F(5) might compute F(3) dozens of times independently.
Memoization (Top-Down)
Think of memoization like taking notes in class. Once you've solved F(3), write it down. Next time you need F(3), just look at your notes instead of re-solving.
You create a storage structure (like a dictionary or array) to cache results. When computing F(n), first check: "Have I solved this before?" If yes, return the stored answer. If no, compute it recursively, store the result, and return it.
This transforms exponential time complexity into linear O(n) time, because each Fibonacci number is computed exactly once.
Tabulation (Bottom-Up)
Tabulation is like filling out a spreadsheet from top to bottom. Instead of recursing from F(n) downward, you start at the base cases (F(0) = 0, F(1) = 1) and iteratively build upward: F(2), F(3), F(4)... until you reach F(n).
You use an array where index i holds F(i). Each entry depends only on the two previous entries, making it straightforward to fill sequentially. No recursion needed—just a simple loop.
Space Optimization
Since each Fibonacci number only needs the previous two values, you don't need to store the entire array. Just keep track of the last two numbers, reducing space complexity from O(n) to O(1).
Key Takeaway: Fibonacci demonstrates the core DP pattern—identify overlapping subproblems (repeated F(k) calls), apply memoization for top-down recursion or tabulation for bottom-up iteration, and optimize space when possible.