Classic 0/1 knapsack, unbounded knapsack, and subset partition problems.
Knapsack DP chooses items to include/exclude to maximize value within a capacity constraint. 0/1 knapsack: each item used at most once. Unbounded: items can repeat. Partition DP extends this to splitting arrays into equal sums.
O(n × W) where W is capacity/target
O(W) with rolling array optimization
Learn the core patterns in this topic. Each block explains when to use the pattern, the intuition behind it, and a compact code example.
dp[i][w] = max value using first i items with capacity w
dp[w] = max value at capacity w, items repeatable
can we pick elements that sum to target? (boolean knapsack)
is there a subset summing to totalSum/2?
0/1: inner loop right to left; unbounded: left to right