Dynamic Programming
Overlapping subproblems plus optimal substructure. Write the recursion, then cache it.
What you actually need to hold in your head
- State is what you must know to decide next
- Memoise top down, then flip to bottom up
- Space optimise by keeping only the rows you read
- Families: knapsack, LIS, LCS, grid, interval, bitmask
Watch it run
Step through the algorithm before you write it.
At every index decide whether to extend the previous best subarray or start fresh from here.
Watch the naive Fibonacci recursion explode, then watch a cache collapse it. This is the moment dynamic programming makes sense.
Each item is taken or skipped under a shared capacity. The table row i, column w is the best value using the first i items within weight w.
Compare the last characters of two prefixes. A match extends the diagonal, a mismatch takes the better of dropping one character from either side.
Fewest coins for each amount from zero upward. Each cell asks: which coin was the last one I used?
Keep the smallest possible tail for each achievable length. Binary search replaces the inner loop and drops the cost to n log n.
Movement is restricted to right and down, which fixes the dependency order: every cell needs the one above and the one to its left.
Cheapest way to turn one string into another using insert, delete and replace. Each cell picks the cheapest of three neighbours.
Patterns in this topic
The trigger phrases are what you are training yourself to notice.
At each index decide whether to extend the previous best or restart from here. One pass, two variables.
Define dp[i] as the answer for the prefix ending at i, then write the recurrence from a constant number of earlier states.
State is index plus remaining capacity. Each item is either taken or skipped, and the table is filled over both dimensions.
Same as 0/1 but an item may be reused, so the transition reads the current row instead of the previous one.
State is a pair of prefixes. When the characters match, consume both; otherwise take the best of the branching options.
Quadratic DP over previous smaller elements, or keep the smallest tail for each length and binary search it for O(n log n).
dp[r][c] depends on the cells you can arrive from, usually up and left. Walk the grid in dependency order.
dp over a range with a split point inside it. Iterate by increasing length so smaller ranges are ready.
Encode the set of used items as bits of an integer and memoise over the mask.
Model holding, sold and resting as states and write the transitions between them per day.
Dynamic Programming problems
Ordered by sheet phase, so the early ones are the highest signal.