Dynamic Programming

Knapsack & Coin Change

Choose items under a capacity: 0/1 and unbounded knapsack, coin change, subset sum.

Hard, about 100 minutes to practise.

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

0
∞
∞
∞
0123

dp[0]=0; others ∞. For each coin, relax every amount ≥ coin.

dp = [0] + [inf]*amount

Live template

Line 1 active

1dp = [inf] * (amount + 1); dp[0] = 0
2for coin in coins:
3 for a in range(coin, amount + 1): # reverse for 0/1
4 dp[a] = min(dp[a], dp[a - coin] + 1)

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.

  1. dp[0] = 0, rest ∞.
  2. For coin 1: every amount a gets dp[a] = min(dp[a], dp[a-1]+1).
  3. Coin 2 and 5 similarly, looping a upward.
  4. 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.

All lessons