What is Dynamic Programming?
Dynamic Programming (DP) is an algorithm design technique that breaks a large problem into smaller subproblems, solves each subproblem once, stores the result, and reuses it when the same subproblem appears again.
"Don't compute the same thing twice" — this simple idea can dramatically reduce time complexity.
Fibonacci: The Best Way to Understand DP
The Fibonacci sequence creates each number by adding the two preceding ones.
F(0) = 0, F(1) = 1, F(n) = F(n-1) + F(n-2)
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...
Approach 1: Naive Recursion — O(2^n)
Computing F(n) by recursively calling F(n-1) and F(n-2) leads to massive redundant computation.
To compute F(5), F(3) is called 2 times, F(2) is called 3 times. As n grows, the number of calls explodes exponentially — O(2^n).
This is exactly the problem DP solves.
Approach 2: Memoization (Top-Down) — O(n)
Store the result of each computation in an array or hash map. When the same input appears again, return the stored value.
Key idea:
- •First time computing F(n): store result in memo[n]
- •Next time F(n) is needed: return memo[n] directly
- •Keep the recursive structure, but eliminate redundant computation
Each F(i) is computed exactly once, giving O(n) time.
Approach 3: Tabulation (Bottom-Up) — O(n)
Solve from the smallest subproblem upward using a loop instead of recursion.
Key idea:
- •Start with dp[0] = 0, dp[1] = 1
- •dp[2] = dp[0] + dp[1], dp[3] = dp[1] + dp[2], ...
- •Fill dp[n] iteratively
Same time complexity as memoization, but no recursion overhead and no risk of stack overflow.
Comparing All Three Approaches
| Approach | Time | Space | Characteristics |
|---|---|---|---|
| Naive Recursion | O(2^n) | O(n) stack | Severe redundancy |
| Memoization | O(n) | O(n) | Top-Down, intuitive |
| Tabulation | O(n) | O(n) → O(1) optimizable | Bottom-Up, stable |
When Can You Apply DP?
1. Optimal Substructure
The optimal solution to the problem can be constructed from optimal solutions of its subproblems.
2. Overlapping Subproblems
The same subproblems are solved multiple times. If there's no overlap, divide and conquer is sufficient.
DP Problems After Fibonacci
Once you understand Fibonacci, try these classic DP problems.
Coin Change — Find the minimum number of coins to make a target amount
0/1 Knapsack — Maximize value within a weight limit
LCS — Find the longest common subsequence of two strings
See It in Action on AlgoNote
Watch how recursive calls overlap in the Fibonacci tree, and how memoization eliminates redundancy — all visualized step by step on AlgoNote. See the core of DP with your own eyes.