Dynamic Programming
Solve each subproblem once, write the answer down, and read it back every other time it is asked for.
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
(1, 1) can be entered from above, 1 way, or from the left, 1 way. Those are disjoint, so 1 + 1 = 2.
In this order
- RecurrenceDefining a value in terms of smaller instances of the same problem.
- StateThe minimal parameters that identify a subproblem; they become the table's dimensions.
- TransitionThe rule that computes one state from earlier states.
- Base CaseStates whose values are known without recursion; they seed the table.
- Overlapping SubproblemsThe same subproblem recurs many times in the naive recursion; that repetition is what memoization removes.
- MemoizationTop-down recursion that caches each result; the recursion tree collapses to one expansion per state.
- TabulationBottom-up filling of the table in an order where dependencies are already computed.
- Optimal SubstructureAn optimal solution is built from optimal solutions of subproblems.
- Fibonaccif(n) = f(n-1) + f(n-2); the smallest example of memoization versus tabulation.
- Climbing StairsWays to reach step n = ways(n-1) + ways(n-2).
- House Robberbest(i) = max(best(i-1), best(i-2) + value(i)); take or skip.
- Unique Grid Pathspaths(r, c) = paths(r-1, c) + paths(r, c-1); Pascal's triangle on a grid.
- Minimum Path Sumcost(r, c) = grid(r, c) + min(cost(r-1, c), cost(r, c-1)).
- Coin ChangeFewest coins for amount a = 1 + min over coins c of best(a - c); ways variant counts combinations.
- Longest Common SubsequenceMatch - diagonal + 1; otherwise max of up and left; trace back to recover the subsequence.
- Edit Distancemin(insert, delete, replace) = 1 + min(left, up, diagonal); match copies the diagonal.
- 0/1 Knapsackdp[i][w] = max(dp[i-1][w], dp[i-1][w - wt] + val); each item is taken at most once.
- Unbounded KnapsackItems may repeat; the transition reads the same row instead of the previous one.
- Longest Increasing SubsequenceO(n^2) DP over predecessors, or O(n log n) with patience sorting and binary search.
- Interval DPFill a triangular table by range length; each range takes the cheapest split into two shorter ranges.
- Tree DPCompute each node's value from its children's values in postorder.
- Bitmask DPA bitmask encodes which elements are used; classic for TSP on small n.
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.
Or a different category
Greedy
One local choice can be proved safe by an exchange argument, so the alternatives never have to be kept.
Divide and Conquer
The subproblems do not overlap; each piece is solved once and never asked about again.