Intro to Dynamic Programming
Understand the core concepts of DP: Overlapping Subproblems and Optimal Substructure.
Examples
The memoized run makes 9 calls: fib(2) and fib(3) are each asked for twice, and the second ask returns from the memo.
fib(1) and fib(0) are base cases, so nothing is reused yet — one value is stored and returned.
What is Dynamic Programming?
Dynamic Programming (DP) is a technique to solve complex problems by breaking them down into simpler subproblems. It stores the results of subproblems to avoid re-computing them.
Key Components:
- Overlapping Subproblems: The problem can be broken down into subproblems which are reused several times.
- Optimal Substructure: The optimal solution of the main problem can be constructed from optimal solutions of its subproblems.
The Motivation (Fibonacci)
Consider calculating the N-th Fibonacci number: F(n) = F(n-1) + F(n-2).
Usually, we might write a simple recursive function. But let's see why that is inefficient.
Attempt 1: Naive Recursion
The obvious recursion, straight from the definition:
def fib(n):
if n <= 1:
return n
return fib(n - 1) + fib(n - 2)
It is correct, and it is unusable past about n = 40. The next section shows why.
Visualizing the Inefficiency
Notice how fib(3) is computed from scratch every time it is asked for. The call tree has 2·fib(n+1) − 1 nodes, so the work grows exponentially — O(2ⁿ).
The Intuition: Cache It!
Why calculate fib(3) twice? Let's just remember the answer the first time we compute it.
This "remembering" is called Memoization (Top-Down DP).
Interactive Visualization
EVERY NODE IS A CALL PLAIN RECURSION MAKES · AMBER = ANSWERED FROM THE MEMO · THE GREY BELOW IT IS WHAT THE CACHE SAVED
LOOK IN THE MEMO
calls made
1
subtrees skipped
0
Answer
—
memo
Nothing cached yet
call stack
Enter fib(5). Not a base case, so look for 5 in the memo
Next
5 is not in the memo, so compute it once: fib(4) + fib(3)
n
n
Legend & Complexity
The call running now
Entered and returned
Answered from the memo — not recursed into
Never entered: the work the memo saved
Time
O(n)
Space
O(n)
Without the memo
O(2ⁿ)
Every node below is a call plain recursion would make. The memoized run lights the ones it actually enters — and an amber node is one that came back from the memo, so nothing underneath it is ever walked. That dim region is the work the cache removed.
Try n = 7: 13 calls against 41.
Dry Run (Memoization)
Calculating fib(5) with memo:
| Call | Cache Status | Action | Result |
|---|---|---|---|
fib(5) |
Empty | Call fib(4) |
Wait |
fib(4) |
Empty | Call fib(3) |
Wait |
fib(3) |
Empty | Call fib(2) |
Wait |
fib(2) |
Empty | Call fib(1), fib(0) |
Returns 1 |
| ... | ... | ... | ... |
fib(3) |
Found fib(2)=1 |
Reuse fib(2) |
Returns 2 |
Edge Cases & Common Mistakes
Watch out for these pitfalls:
Base cases first.
solvehas to answerk <= 1before it looks in the memo, or the recursion has nothing to stop it.One cache key per state. The key has to name the subproblem completely. In a two-dimensional DP that means both indices, not just one.
Deep recursion still overflows. Memoization removes repeated work, not depth. A run of 10⁵ nested calls will exhaust the stack in Python or Java, where the bottom-up form will not.
Solution Template
Top-down memoization — the method the figure above runs. The lines light up as it steps.
Intro to Dynamic Programming Code
1var fib = function(n) {2 const memo = new Map();34 const solve = (k) => {5 if (k <= 1) {6 return k;7 }8 if (memo.has(k)) {9 return memo.get(k);10 }11 const value = solve(k - 1) + solve(k - 2);12 memo.set(k, value);13 return value;14 };1516 return solve(n);17};
When to use DP?
Use DP when:
- Optimization: Finding min/max/shortest/longest.
- Counting: Finding number of ways.
- Feasibility: Is it possible to reach X?