The ideas behind dynamic programming
Dynamic programming solves complex problems by breaking them into overlapping subproblems, solving each once, and reusing the answers. It turns many exponential-time algorithms into polynomial ones.
Origins
Richard Bellman developed dynamic programming in the 1950s for optimising multistage decisions. He later explained that he chose the word 'programming' in the old sense of planning or scheduling, and 'dynamic' because it sounded impressive. It has nothing to do with writing computer programs as such.
Overlapping subproblems
Naive recursion often solves the same subproblem many times. Computing Fibonacci numbers with fib(n) = fib(n - 1) + fib(n - 2) recomputes fib(n - 2) in both branches, and so on down, giving exponential time, about 1.618^n calls. There are only n distinct subproblems, so storing each answer reduces the work to O(n).
Optimal substructure
DP also needs optimal substructure: an optimal solution is built from optimal solutions to subproblems. The shortest route from A to C through B contains a shortest route from A to B. Not every problem has this property: the longest simple path between two vertices does not, which is part of why it is hard.
Top-down memoisation
Memoisation keeps the natural recursive structure but caches results: before computing a subproblem, check a table; after computing it, store it. In Python, the functools.lru_cache decorator memoises a function automatically. Top-down DP solves only the subproblems actually needed, but deep recursion can hit stack limits.
Bottom-up tabulation
Tabulation fills a table iteratively from the smallest subproblems up, in an order that guarantees each entry's dependencies are already computed. For Fibonacci: f[0] = 0, f[1] = 1, then f[i] = f[i - 1] + f[i - 2] for i up to n. It avoids recursion overhead, and often lets you discard old rows to save memory, here keeping just two numbers.
A recipe for DP
First, define the state: what parameters describe a subproblem, such as 'the best answer using the first i items'. Second, write the recurrence relating a state to smaller states. Third, identify base cases. Fourth, choose an evaluation order or memoise. Fifth, if needed, reconstruct the actual solution, not just its value, by recording choices. Complexity is roughly the number of states times the work per state.
Coin change
Given coin values and a target amount, find the fewest coins that make it. Greedy fails for some coin systems. DP state: best[a] = fewest coins to make amount a. Recurrence: best[a] = 1 + min over coins c <= a of best[a - c], with best[0] = 0. For amount A and k coin types, it runs in O(Ak) time. Counting the number of ways to make change is a closely related DP.
Worked example
Coins 1, 3, 4; target 6. best[0] = 0, best[1] = 1, best[2] = 2, best[3] = 1 (one 3), best[4] = 1 (one 4), best[5] = 1 + min(best[4], best[2], best[1]) = 2 (4 + 1), best[6] = 1 + min(best[5], best[3], best[2]) = 1 + 1 = 2 (3 + 3). Greedy would choose 4 + 1 + 1, three coins; DP finds two.
Key takeaways
Dynamic programming, coined by Richard Bellman in the 1950s, needs overlapping subproblems and optimal substructure. Naive Fibonacci recursion is exponential; caching makes it O(n). Memoisation caches recursive calls top-down; tabulation fills a table bottom-up and can save memory. The recipe: define states, write the recurrence, set base cases, choose an order, and reconstruct solutions. Cost is about states times work per state. Coin change shows DP succeeding where greedy fails.
Flashcard
Solve overlapping subproblems once and reuse
Check your understanding
What two properties must a problem have for dynamic programming to help?