Dynamic Programming
Optimal substructure and overlapping subproblems via tables.
The idea
Dynamic programming solves a problem by solving smaller instances of the same problem, and, unlike plain recursion, it solves each distinct instance only once.
It applies when two conditions hold. Optimal substructure: an optimal solution to the whole problem is built from optimal solutions to its subproblems, so the answer satisfies a recurrence over smaller instances. Overlapping subproblems: the recursion reaches the same smaller instances along many different branches. The first condition supplies the recurrence; the second makes storing answers worthwhile. A recursion that merely obeys the recurrence recomputes shared subproblems exponentially many times; recording each answer the first time we produce it removes all the repetition.
There are two ways to record the answers, and they compute the same thing. Memoization keeps the recursion and consults a cache before every call. Tabulation discards the recursion and fills a table of subproblem answers directly.
Algorithm.
Algorithm: Dynamic Programming (tabulation) Input: a problem with optimal substructure and overlapping subproblems Output: the optimal value for the whole instance 1. identify the subproblems, one table cell each // indexed by a few bounded quantities 2. write the recurrence for each subproblem's answer; note the base cases 3. choose a filling order with every cell's dependencies before the cell 4. fill the table in that order: base cases, then each cell once from the recurrence // each cell's dependencies are already filled and correct 5. return the whole problem's answer, read off its cell
The running time is the number of distinct subproblems times the work spent on each one, and the space is the size of the table. Since the subproblems are indexed by a few bounded quantities, that product is polynomial where the naive recursion was exponential.
Ways to work on it
- Walkthrough. Optimal substructure and overlapping subproblems, seen on the longest-common-subsequence recurrence.
- Practice. Fill one cell of a longest-common-subsequence table from its neighbors.
- Hardest. Set up and solve the 0/1 knapsack problem by dynamic programming.
Not sure where to start? Take the ten-question placement test.