Knapsack

A knapsack DP adds a budget to the state. dp[c] holds the best result, or the number of ways, using capacity c, and you sweep that one row once per item.

Variant	Item rule	Loop setup
Unbounded	Reuse an item any number of times	Capacity loop runs upward
0/1	Use each item at most once	Capacity loop runs downward
Combinations vs. sequences	Unordered sets vs. ordered sequences	Items outer vs. capacity outer

Loop order is the whole difference between the variants. Sweeping capacity upward lets dp[c - w] already include the current item, which is right for unlimited coins and wrong for 0/1 knapsack. When counting ways, putting items in the outer loop counts each combination once, whereas putting capacity on the outside counts every ordered sequence separately. Because the table is as wide as the capacity, this approach only works when the budget is reasonably small.

Approach	Time	Extra space
Backtrack over every subset	$O(2^n)$	$O(n)$
Table of items × capacity	$O(nW)$	$O(nW)$
One row, reused per item	$O(nW)$	$O(W)$

Use it when taking an item spends a limited resource, like a total, a weight, or a count of zeros and ones, and the question is the best value or the number of ways to hit a target.

The problems below start with coins, the fewest for a total and the ways to make it with and without order, then switch to 0/1 items for maximum value, the closest even split, and a two-dimensional budget.