Dynamic Programming
Solve each subproblem once, write the answer down, and read it back every other time it is asked for.
DP on a Grid: Paths on a 3 x 4 grid
Dynamic programming starts where plain recursion runs out of time. If a recursive definition calls itself on the same arguments over and over, and naive fib(30) computes fib(10) more than ten thousand times, then the work is not in the problem, it is in the repetition. Storing each answer the first time it is computed removes all of it.
Two routines fill the same table. Memoization keeps the recursion and adds a cache keyed by the arguments. Tabulation drops the recursion and fills the table in an order where every cell's dependencies are already there. They compute the same values. Memoization only visits the states it actually needs and can exhaust the call stack. Tabulation visits every cell and never recurses.
The cost is the number of states times the work per state. 0/1 knapsack over n items and a capacity of W is n * W cells, each reading two earlier cells, so O(n * W) time and the same memory until you notice the transition only reads the previous row. That product is also the trap: a table indexed by a capacity grows with the value of that number, not with the size of the input.
After this you can
- Spot the repeated subproblem in a recursion and name the state that identifies it
- Write a transition and a base case, then fill the table in dependency order
- Convert between a memoized recursion and a bottom-up table, and say why you chose one
- Read the running time off the table: states times work per state
- Cut the memory down to the rows the transition actually reads
In this order
- Recurrence
- State
- Transition
- Base Case
- Overlapping Subproblems
- Memoization
- Tabulation
- Optimal Substructure
- Fibonacci
- Climbing Stairs
- House Robber
- Unique Grid Paths
- Minimum Path Sum
- Coin Change
- Longest Common Subsequence
- Edit Distance
- 0/1 Knapsack
- Unbounded Knapsack
- Longest Increasing Subsequence
- Interval DP
- Tree DP
- Bitmask DP
Also in this category
2D Dynamic Programming
1D Dynamic Programming
Advanced Dynamic Programming
Where people go wrong
Caching on an incomplete key
If two different subproblems share a cache key, the answer stored for the first is returned for the second. Every parameter the transition depends on belongs in the state: the item index and the capacity left, not the index alone.
A recurrence without optimal substructure
The table only works when an optimal whole is built from optimal parts. The longest simple path in a graph is not: the best route into a node can use vertices a later step still needs, so the parts cannot be combined.
Pseudo-polynomial tables
O(n * W) reads like a small product, but W is a value taken from the input rather than its length. A capacity of 10^9 is a billion columns per item however few items there are.