DP Patterns (Knapsack, LCS, LIS, Coin Change)
The four canonical DP patterns: 0/1 knapsack (include or exclude items), LCS (align two sequences), LIS (find longest increasing subsequence), coin change (minimum coins for a target).
DP patterns = four kitchen recipes. Knapsack = packing a lunchbox (pick items, don't exceed weight). LCS = aligning two DNA strands. LIS = stacking boxes by size. Coin change = making exact change at a vending machine with limited denominations.
0/1 Knapsack: dp[i][w] = max value using first i items with weight capacity w. O(n*W) time and space, O(W) space with rolling. LCS: dp[i][j] = LCS of s1[0..i-1] and s2[0..j-1]. O(m*n) time and space. LIS: dp[i] = length of LIS ending at index i. O(n²) DP or O(n log n) with patience sorting (binary search). Coin Change: dp[amount] = min coins. O(amount * num_coins), equivalent to BFS on an implicit graph.
Knapsack generalizes: unbounded knapsack allows infinite copies of each item — iterate amounts forward. Subset sum is 0/1 knapsack with weights=values, target capacity. LCS generalizes to edit distance (add/delete/replace operations), longest palindromic subsequence (LCS of s and reversed s). LIS with O(n log n): maintain a 'tails' array where tails[i] is the smallest tail element of all increasing subsequences of length i+1. Binary search for insertion point. Coin change generalizes to all DP on DAGs where you accumulate a cost — think of it as shortest path on a graph where each amount is a node.
When I see a DP problem, I identify which canonical pattern it resembles. 'Maximize value given a constraint' → knapsack. 'Align two sequences' → LCS/edit distance family. 'Subsequence of one sequence' → LIS family. 'Minimum steps/coins to reach target' → coin change / BFS on implicit graph. Then I define the state, write the recurrence, handle base cases, and optimize space if possible. The hardest part is always the state definition — I make sure it captures exactly enough information to make the optimal decision.
0/1 knapsack iterates capacity in DECREASING order when using a 1D array — this ensures each item is used at most once. Iterating forward (unbounded knapsack order) allows the same item to be counted multiple times. Swapping these two iteration directions is the most common knapsack bug.