Four patterns to remember:
Two dimensions: items processed and capacity remaining.
Binary choice: for each item, take it or skip it.
Transition looks back: depends only on .
space reduction: reverse the inner loop to use a 1D (one-dimensional) array. These patterns apply to many problems. Subset sum, partition problems, and bounded resource allocation all follow the same structure. If you can see "choose items under a limit," think knapsack.