Card 10/ 10
Recap: Dynamic Programming
Define the state, check the recurrence by hand, compute each entry once, and cost it as states times work.
Dynamic programming solves a problem from the stored answers to its overlapping subproblems, computing each one once. This card gathers what the topic established and where each idea was taught.
| The idea | Where |
|---|---|
| A problem suits dynamic programming when its subproblems overlap and its best answer is built from best answers to smaller ones; fib(5) by plain recursion made 15 calls for 6 distinct values | Dynamic Programming: Solving Each Subproblem Once |
| Design starts from a state in one sentence and a recurrence, checked by hand on a small input: 3, 2, 7 and 10 give 13 | Define a State and a Recurrence, Then Check Them by Hand |
| Adding the value to the wrong term lets neighbours both be taken, and the answer silently grows | Swapping the Two Choices in the Recurrence |
| Memoisation computes states on demand through recursion; tabulation fills a table in dependency order; both cost the same | Top-Down With Memoisation, Bottom-Up With a Table |
| Python caches with functools.cache; Java and TypeScript use a map read before the work and written after | Memoised and Tabulated Solutions in Python, Java and TypeScript |
| Deep inputs overflow the call stack in every language, so long chains of states call for a table | Memoisation vs Tabulation |
| A recurrence that reads the k entries before it needs only k variables, at the price of recovering the choices | Keeping Only the Entries the Recurrence Reads |
| Cost is states times work per state; a factor that is a value, such as a capacity, makes it pseudo-polynomial | Costing a Dynamic Programme: States Times Work per State |
| Counting problems use the same design, with sums in place of maximums: 1226 has 5 readings | Practice: Counting the Readings of a Door Code |
Every dynamic programme in the topic is costed the same way, and the table below gives the figures for the three it built.
| Problem | State | Time | Space, rolled |
|---|---|---|---|
| Fibonacci | fib(i) | O(n) | O(1) |
| No neighbours | Best total from the first i stalls | O(n) | O(1) |
| Door code | Readings of the first i digits | O(n) | O(1) |
All three have one index. Knapsack and Grid Dynamic Programming, the next topic, gives the state a second index, and the cost becomes the area of a table.
← → move through sections and cards