1Understand
The idea
dp[c] is the best you can do with capacity (or target sum) c. For 0/1 items, loop the capacity downwards so each item is used at most once; for unlimited items, loop it upwards so an item can be reused. Coin change, subset sum and partitioning are all this table.
Intuition
dp[c] is the best you can do with capacity (or target sum) c. For 0/1 items, loop capacity downwards so each item is used at most once; for unlimited items, loop upwards so an item can be reused.
Coin change, subset sum and partition are the same table with different interpretations of "best" (max value, min coins, reachability bool).
The loop direction is the whole trick. Get it wrong and you silently allow illegal reuse.
What you will be able to do
- Choose loop order for 0/1 vs unbounded
- Distinguish counting from optimising
When to use it
- Reach an exact total with items/coins
- Maximise value under a weight limit
- Partition into equal sums
2See it
Walkthrough
Coin change (unbounded)
coins = [1, 2], amount = 3, min coins to make amount.
1 / 5
dp[0]=0; others ∞. For each coin, relax every amount ≥ coin.
Live template
Line 1 active
Complexity: time O(n·W), space O(W)
Time O(n · capacity), space O(capacity). Exponential subset enumeration fails for large capacity. If capacity is huge but n is tiny, meet-in-the-middle may beat DP.
Read the walkthrough as text
Coin change (unlimited). Coins [1,2,5], amount 11.
dp[0] = 0, rest∞.- For coin
1: every amount a getsdp[a] = min(dp[a], dp[a-1]+1). - Coin
2and5similarly, looping a upward. dp[11] = 3(5+5+1).
For 0/1 subset sum to target, iterate items outer and capacity from target down to w.
3Recognise it
Kinds of problems (6)
Same pattern, different surfaces. Each row is a problem shape you should recognise, not only the first walkthrough example.
Coin change (fewest coins)
Example. Minimum coins to make amount.
How. Unbounded: coins outer, capacity inner ascending; dp[a] = min over coins.
Coin change (number of ways)
Example. Count combinations to form amount.
How. Coins outer loop, capacity inner, order of loops counts combinations not permutations.
0/1 knapsack
Example. Max value with each item once.
How. Capacity loops backward from W; dp[w] = max(skip, take).
Partition equal subset sum
Example. Can array split into two equal sums?
How. 0/1 knapsack to target sum/2 on the array.
Target sum with + and −
Example. Assign signs to reach target sum.
How. Reduce to subset sum: (target + total)/2 must be achievable.
Grouped knapsack (pick from piles)
Example. At most one from each pile of items.
How. Outer pile loop; inner capacity backward over pile items, nested 0/1 per pile.
Common mistakes
Failure modes the tutor watches for. Open the Common mistake tab in the walkthrough to watch one fail live.
Wrong loop direction
Why it happens. Forward capacity loop matches the unbounded coin pattern.
How it fails. 0/1 knapsack iterates w upward, item i counted twice in same knapsack.
Fix. 0/1: for w from W down to weight[i]. Unbounded/coins: forward.
Greedy coins
Why it happens. Largest coin first minimises count for real currency.
How it fails. Coins [1,3,4], amount 6: greedy 4+1+1=3 coins; DP needs two 3’s.
Fix. Unless proven canonical, use DP for fewest coins.
Combinations vs permutations
Why it happens. Two nested loops over coins and amount always feel symmetric.
How it fails. Coin change ways: amount outer, coins inner, counts permutations, not combinations.
Fix. Combinations: coins outer, amount inner ascending.
Unreachable totals
Why it happens. inf means “bad” and callers can interpret.
How it fails. Return dp[amount]==inf as the count of ways, wrong type/meaning for “impossible”.
Fix. Map unreachable to -1 (or separate sentinel) per problem statement.
4Check yourself
Concept check
A short quiz on this lesson before you practise. Optional, and it does not gate coding.
Ready to practise?
Mastery comes from solving. The lesson is optional context.