Fibonacci with Dynamic Programming

Why Fibonacci?

Fibonacci is the "Hello World" of dynamic programming. It perfectly illustrates how a problem with overlapping subproblems goes from exponentially slow to blazingly fast with DP. Every DP technique — memoization, tabulation, and space optimization — can be demonstrated with Fibonacci before applying them to harder problems.

The Fibonacci sequence: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ... Definition: F(n) = F(n-1) + F(n-2) with F(0) = 0, F(1) = 1

Approach 1: Naive Recursion — O(2^n)

This directly translates the mathematical definition. But the recursion tree explodes:

fib(3) is computed 3 times. fib(2) is computed 5 times. For fib(n), the total calls are approximately 2^n. Computing fib(50) would take over a million billion operations — days on modern hardware.

Time: O(2^n) — exponential Space: O(n) — recursion depth

Approach 2: Memoization — O(n)

Store each result the first time we compute it. Return cached result on subsequent calls.

Now the recursion tree is pruned — each fib(k) is computed only once:

Only n unique subproblems exist, each solved once with O(1) work.

Time: O(n) — n subproblems, O(1) per subproblem Space: O(n) — cache stores n values + O(n) recursion stack

Approach 3: Tabulation — O(n) time, O(n) space

Build the table from the bottom up. No recursion needed.

We fill the table left to right. When we compute dp[i], both dp[i-1] and dp[i-2] are already filled. Simple, fast, no recursion overhead.

Time: O(n) Space: O(n) — the dp array

Approach 4: Space Optimized — O(n) time, O(1) space

Key observation: dp[i] only needs dp[i-1] and dp[i-2]. We do not need the entire array — just the last two values!

Time: O(n) Space: O(1) — just two variables!

C++ Implementations

Performance Comparison

Bonus: Matrix Exponentiation — O(log n)

There is actually an O(log n) solution using the identity:

Time: O(log n) — via fast matrix exponentiation Space: O(1) — constant size matrices

This technique generalizes to any linear recurrence (Tribonacci, linear DP transitions, etc.).

The Bigger Picture

Fibonacci teaches the DP progression that applies to ALL DP problems:

1. Start with brute-force recursion (correct but slow)
2. Add memoization (fast, easy change)
3. Convert to tabulation (no stack overflow)
4. Optimize space (if possible)

Master this progression on Fibonacci, then apply the same thinking to knapsack, LCS, edit distance, and every other DP problem.