Definition
Dynamic programming (DP) solves a problem by breaking it into overlapping sub-problems and saving each answer so it's only computed once. It can be top-down with memoisation, or bottom-up by filling a table.
In simple words
What's 1+1+1+1+1? You count: 5. Add another +1. You don't recount, you say 6, because you remembered. That's DP: remember earlier answers, so you don't redo the work.
Why it matters
It turns slow exponential solutions into fast ones. Viterbi in NLP and the Bellman equations in RL are both DP, and DP is a favourite topic in coding interviews.
How it works
- Define the state: what does each sub-problem need to know?
- Write the relation between a state and smaller states.
- Set the base cases.
- Compute, either with a cache or by filling a table.
| Style | How | Note |
|---|---|---|
| Top-down | Recursion plus a cache | Natural to write |
| Bottom-up | Loops that fill a table | No recursion limit |
The maths
In code
from functools import lru_cache
calls = {"plain": 0}
def fib_plain(n):
calls["plain"] += 1
return n if n < 2 else fib_plain(n - 1) + fib_plain(n - 2)
@lru_cache(maxsize=None)
def fib_memo(n):
return n if n < 2 else fib_memo(n - 1) + fib_memo(n - 2)
print(fib_plain(25), "using", calls["plain"], "calls")
print(fib_memo(25), "using", fib_memo.cache_info().misses, "computed values")
def fewest_coins(amount, coins=(1, 5, 10)):
best = [0] + [amount + 1] * amount
for value in range(1, amount + 1):
for coin in coins:
if coin <= value:
best[value] = min(best[value], best[value - coin] + 1)
return best[amount]
print("Fewest coins for 28:", fewest_coins(28))Output
75025 using 242785 calls 75025 using 26 computed values Fewest coins for 28: 6
Common mistakes
- Forgetting the base case, which leads to a RecursionError.
- Using DP without overlapping sub-problems. Then there's nothing to reuse.
Check yourself
Summary
- DP stores sub-problem answers to avoid repeating work.
- Top-down uses a cache, and bottom-up fills a table.
- Viterbi and Bellman updates are DP too.
Finished reading?