Dynamic Programming and Memoization
Turn exponential recursion into linear-time code by remembering what you already computed
Big Idea: Many recursive solutions re-solve the same subproblem thousands of times. Dynamic programming (DP) is the discipline of solving each distinct subproblem once and reusing the answer. Memoization is the top-down way to do that: keep a cache keyed by the arguments. Tabulation is the bottom-up way: fill a table from the smallest subproblems upward. Same recurrence, two directions.
By the end you will be able to:
- recognise the two signals that DP applies: overlapping subproblems and optimal substructure,
- convert a naive recursion into a hand-rolled memo dictionary,
- reach for
functools.lru_cachewhen the arguments are hashable, - rewrite a top-down solution as a bottom-up tabulation,
- apply all of this to Fibonacci, coin change and the 0/1 knapsack problem,
- reason about the time and space trade-offs honestly.
This is an advanced capstone. It assumes you are comfortable with recursion, Big-O notation, closures and functools from the earlier decorators topic. We build on those directly rather than re-teaching them.
1. When does DP apply? Two preconditions
Dynamic programming is not a trick you sprinkle on any slow function. It is an optimisation that only pays off when a problem has both of these properties:
- Overlapping subproblems. The recursion keeps asking for the answer to the same smaller instance. If every subproblem were unique, there would be nothing to cache and DP would add overhead for no gain. (Plain divide-and-conquer such as merge sort has no overlap, which is why memoizing it does nothing.)
- Optimal substructure. The optimal answer to the whole problem can be built from optimal answers to its subproblems. This is what lets you combine cached results correctly instead of re-deriving them.
Fibonacci, shortest paths, coin change and knapsack all satisfy both. When you see a recurrence that calls itself on overlapping ranges, DP is the tool.