Dynamic programming
Some problems ask the same smaller questions over and over. Plain recursion for the 30th Fibonacci number makes over 2.6 million calls, yet there are only 31 different questions. Dynamic programming stores each answer once and reuses it. Watch a table of memory cells fill left to right, first with Fibonacci numbers, then with the fewest coins for each amount.
5 quick questions
Pick an answer to see why. Your score saves with your progress.
01Plain recursive fib(n) calls fib(n-1) and fib(n-2). Why is it so slow for fib(30)?
The questions overlap: fib(28) is needed by both fib(30) and fib(29), and so on down. Plain recursion recomputes each one every time, which makes 2,692,537 calls.
02What does putting @cache (from functools) above a recursive function do?
That is memoization, the top-down form of dynamic programming. With @cache, fib(30) works out each of its 31 answers only once.
03In the bottom-up table t for Fibonacci, why do we fill the cells from left to right?
t[i] = t[i-1] + t[i-2] reads two earlier cells. Filling in increasing order means every cell a step reads is ready.
04With coins worth 1, 3 and 4, what is the fewest number of coins that make 6?
3 + 3 = 6 uses two coins. Taking the biggest coin first gives 4 + 1 + 1, three coins, so the greedy shortcut is not always best.
05Which two properties tell you dynamic programming fits a problem?
Overlapping subproblems means the same smaller questions come up many times; optimal substructure means the best answer is built from best answers to smaller questions.
Glossary
- Dynamic programming
- Solving a problem by breaking it into smaller questions, solving each one only once and storing the answers to build bigger ones.
- Subproblem
- A smaller version of the same question, such as fib(5) inside fib(7), or making 3 when you need to make 6.
- Overlapping subproblems
- When the same subproblems come up many times, so storing their answers saves repeated work.
- Optimal substructure
- When the best answer to a problem is built from the best answers to its subproblems.
- Memoization
- Top-down: keep the recursive code, but store each result the first time and return the stored one on repeat calls. In Python, functools.cache does this.
- Tabulation
- Bottom-up: fill a table of answers in an order where every cell's inputs are already filled, usually with a loop.
- Base case
- An answer known without any work, such as fib(0) = 0 and fib(1) = 1, or 0 coins to make 0.
- Greedy
- Always taking the choice that looks best right now, such as the biggest coin. Fast, but not always correct.
Notes and sources
- Plain recursion calls fib(n) 2 × F(n+1) − 1 times in total (the Leonardo numbers): 41 for fib(7) and 2 × 1,346,269 − 1 = 2,692,537 for fib(30). The ratio between one count and the next tends to the golden ratio, about 1.618.
- @cache arrived in Python 3.9 and is the same as @lru_cache(maxsize=None). For fib(30), cache_info() reports 31 misses (answers worked out) and 28 hits (answers read back).
- Memoized recursion still goes one call deeper for each n. CPython stops at about 1000 nested calls by default (sys.getrecursionlimit()), so fib(5000) with @cache raises RecursionError, while the table loop has no such limit.
- Taking the biggest coin first gives the fewest coins for some coin systems, such as 1, 5, 10 and 25, but not for every system, as 1, 3 and 4 show. Dynamic programming is correct for any set of coins.
- The name comes from Richard Bellman, who developed the method in the 1950s; "programming" there means planning, not writing code.
- Python library: functools.cache and lru_cache
- Python library: sys.getrecursionlimit
- Jeff Erickson, Algorithms, chapter 3: Dynamic Programming (University of Illinois)
- MIT 6.006 Introduction to Algorithms (Fall 2011), dynamic programming lectures
- Cormen, Leiserson, Rivest and Stein, Introduction to Algorithms, 4th ed. (MIT Press), chapter 14
- OEIS A000045: Fibonacci numbers
- OEIS A001595: Leonardo numbers (calls made by plain recursive Fibonacci)
Quiz Unlocks after the last step.