L38 · DP VI — Unbounded Knapsack

Series: LeetCode — From Basics to Interview-Ready · Session 38 / 65 · Phase 2 · Dynamic programming

Prerequisites

L37 (0/1 knapsack) is mandatory — this session is defined as its opposite. If you cannot yet say "0/1 sweeps capacity backwards", stop and finish L37 first. Everything here is the same table with the inner loop reversed.

Watch first (skim before the session)

Why this session exists

Unbounded knapsack is 0/1's mirror image, and interviewers test whether you can tell them apart under pressure. The naked version — "items with weight and value, capacity W, each item usable unlimited times, maximise value" — is rare; the disguises are everywhere: Coin Change (fewest coins), Coin Change 2 (how many ways), Rod Cutting (best price to cut a rod), Combination Sum IV (count ordered ways to reach a target).

Two details carry this session. First: the single-character difference from 0/1 — the capacity loop runs forwards so dp[c-w] already includes the current item, making it reusable. Second, and subtler: for the counting variants, the order of the two loops decides whether you count combinations (item loop outside) or permutations (capacity loop outside). That loop-order distinction is a favourite senior-level probe.

Blank-file warm-up

Five minutes, empty file, no notes. Write both cores from memory, and note the one flipped line:

unbounded value :  for c from w to W:            # FORWARDS (reusable)
                        dp[c] = max(dp[c], dp[c-w] + v)
 
coin change min :  for c from coin to amount:    # FORWARDS
                        dp[c] = min(dp[c], dp[c-coin] + 1)

If the loop direction wobbles against L37, drill the pair: "one-of-each backwards, unlimited forwards."

From first principles

Unbounded value maximisation (the naked form):

def unbounded_knapsack(weights: list[int], values: list[int], W: int) -> int:
    dp = [0] * (W + 1)
    for c in range(1, W + 1):
        for w, v in zip(weights, values):
            if w <= c:
                dp[c] = max(dp[c], dp[c - w] + v)   # reuse allowed: dp[c-w] may include this item
    return dp[W]
 
assert unbounded_knapsack([1, 3, 4], [15, 50, 60], 8) == 130   # 4+4 -> 60+60

Coin Change — the canonical disguise

Fewest coins to make an amount, coins reusable — unbounded knapsack minimising count.

def coin_change(coins: list[int], amount: int) -> int:
    INF = amount + 1
    dp = [INF] * (amount + 1)
    dp[0] = 0                                 # 0 coins make amount 0
    for c in range(1, amount + 1):
        for coin in coins:
            if coin <= c:
                dp[c] = min(dp[c], dp[c - coin] + 1)   # forwards: reuse coins
    return dp[amount] if dp[amount] != INF else -1
 
assert coin_change([1, 2, 5], 11) == 3       # 5 + 5 + 1
assert coin_change([2], 3) == -1             # impossible
assert coin_change([1], 0) == 0

• Complexity: O(amount · len(coins)) time, O(amount) space.
• Follow-up: return the actual coins (parent pointers), or count the number of ways (Coin Change 2), which flips it to a counting problem with a loop-order subtlety.

Coin Change 2 — where loop order bites

Count the number of combinations of coins that make the amount. Coins outer, amount inner:

def coin_change_2(amount: int, coins: list[int]) -> int:
    dp = [0] * (amount + 1)
    dp[0] = 1                                 # one way to make 0: take nothing
    for coin in coins:                        # coins OUTER  -> counts combinations
        for c in range(coin, amount + 1):     # forwards -> reusable
            dp[c] += dp[c - coin]
    return dp[amount]
 
assert coin_change_2(5, [1, 2, 5]) == 4      # {5},{2,2,1},{2,1,1,1},{1x5}
assert coin_change_2(3, [2]) == 0

If you swap the loops (amount outer, coins inner) you count permutations instead — [1,2] and [2,1] become distinct — which is Combination Sum IV, a different problem. This is the senior probe.

Memory hook

"Unlimited, sweep forwards — coins outside for combos, target outside for orders." The first clause pairs with L37's "one of each, sweep backwards." The second clause encodes the only genuinely tricky bit of this session — the counting loop order. Recite the full pair (L37 + L38) as one sentence and both knapsacks are locked.

What interviewers actually ask

• LC322 · Coin Change — Amazon, Google. Fewest coins for an amount. Probe: recognising unbounded knapsack, the forward loop, and the "impossible ⇒ -1" sentinel. Follow-up: reconstruct the coins, or handle huge amounts.
• LC518 · Coin Change 2 — Amazon. Count combinations. Probe: the coins-outer loop order and why it counts combinations not permutations. This is the discriminating question.
• LC377 · Combination Sum IV — Google. Despite the name, it counts permutations (ordered), so it's the capacity-outer twin of Coin Change 2. Probe: can you articulate that the loop order flips the meaning?
• LC279 · Perfect Squares — Amazon. Fewest perfect squares summing to n = Coin Change with coins = {1,4,9,16,...}. Probe: seeing the reduction, and the sqrt bound on the coin set.
• LC983 · Minimum Cost For Tickets — Google. An unbounded-flavoured DP over days with 1/7/30-day passes. Probe: state as cost-to-cover-up-to-day-i with reusable passes.
• LC518 vs LC377 side by side — interviewers sometimes ask both to see if you truly understand loop order versus having memorised one template.

Escalation ladder: fewest items (min) → count combinations → count permutations → reconstruct the multiset. The middle two are the same DP with the loops swapped — the whole point of the session.

Tradeoff

In practice

Making change is the textbook example, but the same DP powers cutting-stock optimisation (cut raw material into pieces to maximise value — Rod Cutting is literal unbounded knapsack) and billing/pass-selection systems that pick the cheapest combination of reusable passes to cover a period. Whenever a resource is available in unlimited units and you're optimising or counting ways to hit a target, unbounded knapsack is the engine.

Practice queue

Solve in this order; log each as cold / warm / hint / failed.

1. LC322 Coin Change — unbounded min, the gateway.
2. LC518 Coin Change 2 — count combinations (coins outer).
3. LC377 Combination Sum IV — count permutations (target outer); feel the flip.
4. LC279 Perfect Squares — Coin Change with square coins.
5. LC983 Minimum Cost For Tickets — unbounded-flavoured day DP.