Dynamic Programming
Knapsack DP
When you see it
Signal words
If the prompt uses any of these, this pattern should come to mind first.
subset sumpartitioncoin changetarget sumcapacitychoose items
Practice
Drill this pattern with an AI trainer — reply only with Hint, Next, Lost, or paste your code.
Ask yourself
- Choose a subset under a capacity/target?
- Coin change / partition / subset-sum?
dpover (item, remaining capacity).
Classic problem
0/1 Knapsack — Given items with weights and values, and a capacity W, find the maximum value that fits in the knapsack. Each item can only be used once.
Input: items = [[1,1],[2,3],[3,4],[2,2]], capacity = 5
Output: 7 — take item [2,3] and [3,4] (total weight 5, total value 7).
Common pitfalls
Iterating capacity upward for 0/1 (double-counts items).
Confusing bounded vs unbounded knapsack loops.