Lessons from 0/1 Knapsack

Four patterns to remember:

$1.$ Two dimensions: items processed and capacity remaining.

$2.$ Binary choice: for each item, take it or skip it.

$3.$ Transition looks back: $dp[i]$ depends only on $dp[i-1]$.

$4.$ 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.