Sonith ManakkatSome problems contain smaller copies of themselves. Open a Russian doll and there is a slightly smaller doll inside, then another, until the last one cannot be opened. That is recursion. It is a natural way to describe many solutions, but it has a trap: a careless version can do the same work millions of times. Dynamic programming is the cure, and it is one of the most useful ideas in algorithms. Each section has a plain picture and an Expert view.
Recursion: the Russian dolls
Every sound recursive solution has two parts:
- Base case. The smallest version, answered directly. It stops the recursion.
- Recursive case. Reduce the problem to a smaller one of the same kind, solve that, and combine.
factorial(n):
if n is 0: return 1 // base case
return n times factorial(n - 1) // recursive case
countdown(n):
if n is 0: say "go"; return // base case
say n
countdown(n - 1) // recursive caseExpert viewStack depth and tail calls
Each call that has not finished is kept on the call stack, so recursion to depth n uses O(n) stack space. Most languages cap that depth, so a very deep recursion can fail with a stack overflow even if the logic is right. A tail call is a recursive call that is the very last thing a function does; some language implementations can reuse the current stack frame for it, turning such recursion into a loop. Whether that happens depends on the language and its implementation, and many common languages do not guarantee it. Where depth could be large, rewrite as a loop or use an explicit stack.
The trap: naive Fibonacci
The Fibonacci numbers start 0, 1, 1, 2, 3, 5, 8 and each is the sum of the two before. The recursive definition is tempting:
fib(n):
if n is 0 or 1: return n
return fib(n - 1) + fib(n - 2)Show the 9 steps as text
- Fibonacci: each number is the sum of the two before it. Start with 0 and 1.
- fib(2) = 1 + 0 = 1. Written down once, never recomputed.
- fib(3) = 1 + 1 = 2. Written down once, never recomputed.
- fib(4) = 2 + 1 = 3. Written down once, never recomputed.
- fib(5) = 3 + 2 = 5. Written down once, never recomputed.
- fib(6) = 5 + 3 = 8. Written down once, never recomputed.
- fib(7) = 8 + 5 = 13. Written down once, never recomputed.
- fib(8) = 13 + 8 = 21. Written down once, never recomputed.
- fib(9) = 21 + 13 = 34. Written down once, never recomputed.
- fib(10)about 177 calls
- fib(30)about 2.7 million calls
- fib(50)over 40 billion calls
Expert viewWhy it is exponential
The number of calls to compute fib(n) this way grows roughly like 1.618 to the power n (the golden ratio), which is exponential: adding one to n multiplies the work by about 1.6. The tree of calls is deep on the left (n levels) but contains only n + 1 distinct subproblems, fib(0) up to fib(n). The waste is repeated work on identical subproblems.
The fix: remember answers
Memoisation means storing each answer the first time you compute it, and looking it up afterwards.
memo = empty table
fib(n):
if n is 0 or 1: return n
if n is in memo: return memo[n]
memo[n] = fib(n - 1) + fib(n - 2)
return memo[n]Now each of the n + 1 values is computed once, so the time drops from exponential to O(n), with O(n) memory for the table (plus recursion depth).
When does it apply?
Overlapping subproblems
- The same small questions come up again and again
- So storing answers saves work
Optimal substructure
- A best answer is built from best answers to smaller pieces
- So combining stored answers is valid
Expert viewRecognising a DP problem
Look for: a question asking for a count, a minimum, a maximum or "is it possible"; choices made step by step; and a way to describe the situation after some choices as a small state (for example "the amount left" or "the first i items and capacity c"). Then write a recurrence that gives the answer for a state from answers to smaller states, name the base cases, and decide the order of evaluation. If subproblems do not overlap (as in merge sort, where pieces are disjoint) memoising gains little; that is plain divide and conquer, covered in part 7. If optimal substructure fails, DP gives wrong answers even though it runs.
Coin change: where the greedy idea fails
You must pay an amount using as few coins as possible. The coin values are 1, 3 and 4, and the amount is 6.
Greedy: biggest coin first
- 4, then 1, then 1: three coins
- Looks sensible but is not the fewest
Dynamic programming
- 3 and 3: two coins
- Tries each coin as the last one and uses stored answers
Show the 8 steps as text
- Goal: fewest coins (1, 3 or 4) for each amount up to 6. Zero coins make 0.
- Amount 1: best is 1 coin, reusing the answers for 0.
- Amount 2: best is 2 coins, reusing the answers for 1.
- Amount 3: best is 1 coin, reusing the answers for 2, 0.
- Amount 4: best is 1 coin, reusing the answers for 3, 1, 0.
- Amount 5: best is 2 coins, reusing the answers for 4, 2, 1.
- Amount 6: best is 2 coins, reusing the answers for 5, 3, 2.
- Answer for 6 is 2 coins (3 + 3). Grabbing the biggest coin first would take 3 (4 + 1 + 1).
best[0] = 0
for amount from 1 up to target:
best[amount] = infinity
for each coin that is not bigger than amount:
best[amount] = min(best[amount], 1 + best[amount - coin])Expert viewCoin change costs
With a target amount n and k coin types this runs in O(n times k) time and O(n) space. Notice it is not polynomial in the number of digits of the amount, so it is fine for moderate amounts. To recover which coins to use, remember the coin that gave each minimum. With standard coin sets, greedy happens to give the optimal answer, but that depends on the set, which is why the 1, 3, 4 case is the classic counterexample.
Knapsack, by intuition
The problem
- Each item has a size and a value; the bag has limited room
- Pick items to get the most total value
The idea
- Ask: for the first few items and a given room, what is the best value?
- Each item is either left out or taken, and both options use smaller answers
In words: for each item, there are two choices. Leave it, and the best value is whatever the earlier items gave for the same room. Take it, and the best value is its value plus what the earlier items give for the room left after it. Keep the larger. Fill a table with the items down one side and room along the other, and the bottom corner holds the answer.
Expert viewSpace and time for the table
The usual 0/1 knapsack table has (number of items) times (capacity) cells, so O(n times W) time. Because each row depends only on the previous row, you can keep one row and reduce memory to O(W), provided you update the capacities in the right order (from high to low for 0/1 knapsack). The same trick works for many tables, such as coin change (already one-dimensional) and edit distance. Note that O(n times W) depends on the numeric size of W, so knapsack is not known to be solvable in time polynomial in the length of its input; I mention the fact without going further.
Top-down or bottom-up
Top-down (memoisation)
- Start at the big question; recurse and store
- Computes only the answers actually needed
Bottom-up (table)
- Start at the smallest cases and fill upward
- No recursion depth worries; easy to save memory
Side by side
| Problem | Plain recursion | With DP | DP space |
|---|---|---|---|
| Fibonacci | exponential | O(n) | O(n), or O(1) keeping two values |
| Coin change (target n, k coins) | exponential | O(n times k) | O(n) |
| 0/1 knapsack (n items, capacity W) | O(2 to the n) | O(n times W) | O(W) with one row |
Try it by hand
- Write a row 0 to 7Under it write best[0] = 0
- Amounts 1 and 2Only coin 1 fits, so best is 1 and 2
- Amounts 3 and 4Coin 3 gives 1 for amount 3; coin 4 gives 1 for amount 4
- Amounts 5 and 65: one coin plus best[4] is 2; 6: coin 3 plus best[3] is 2
- Amount 7Try 1 + best[6], 1 + best[4], 1 + best[3]; the smallest wins
- Read off the coinsSeven is 3 + 4, so the answer is 2 coins
Do not solve the same small problem twice: write the answer down.
Frequently asked questions
Is dynamic programming the same as recursion?
No. Recursion is a way of writing a solution. DP is the idea of storing sub-answers; it can be written recursively (top-down) or with loops (bottom-up).
Why is it called dynamic programming?
It is a historical name, and "programming" there means planning or scheduling, not writing code.
Is memoisation always worth it?
Only when subproblems repeat. Otherwise it costs memory and gains nothing.
Does greedy ever work for coin change?
Yes, for some coin sets, such as many everyday currencies, but not for all, as the 1, 3, 4 case shows.