Lab 06 — Greedy Vs DP (Coin Change Counterexample)

Goal

Internalize the failure mode of greedy by walking through the canonical counterexample: coin change with denominations [1, 3, 4] and target 6. Greedy gives 4 + 1 + 1 = 3 coins; DP gives 3 + 3 = 2 coins. Make this the test you run on every “looks like greedy” problem before committing.

Background

Many candidates correctly solve coin change with US denominations [1, 5, 10, 25] greedily, then assume greedy works for any denomination set. It does not. The failure on [1, 3, 4] target 6 is the most-cited counterexample in algorithms textbooks (Cormen, Kleinberg-Tardos, Erickson) precisely because it cleanly demonstrates that “greedy felt right” is not a proof. The lesson generalizes: for greedy to work on a problem, the underlying combinatorial structure typically must be a matroid — a property that is rarely obvious from problem statements and almost never holds for arbitrary inputs.

Interview Context

This lab is the meta lab of Phase 6. Its purpose is not to drill a new algorithm but to drill the discipline of testing greedy hypotheses against counterexamples before coding. Interviewers love to ask coin-change variants specifically because they expose candidates who pattern-match without proof. A candidate who says “I’ll greedy by largest denomination” is asked “what about [1, 3, 4] target 6?” and either (a) recovers gracefully and switches to DP, or (b) doubles down and ships wrong code. (b) ends the interview.

Problem Statement

Given an array of distinct positive coin denominations coins and a non-negative integer amount, return the minimum number of coins needed to sum to amount, or -1 if impossible. You have an unlimited supply of each denomination.

LeetCode reference: LC 322 — Coin Change.

Constraints

  • 1 ≤ |coins| ≤ 12
  • 1 ≤ coins[i] ≤ 2^31 - 1
  • 0 ≤ amount ≤ 10^4
  • Coins are distinct. 1 may or may not be in the set; if not, some amounts are unreachable.

Clarifying Questions

  1. “Are coins guaranteed sorted?” — typically no; sort if needed.
  2. “Is 1 always present?” — no; the input coins = [3, 5] and amount = 4 is unsolvable, return -1.
  3. “Can amount = 0?” — yes; answer is 0.
  4. “Is the order of coins in the answer significant?” — no, just the count.
  5. “Should I count the coins or list them?” — count.

Examples

  • coins = [1, 3, 4], amount = 6 → 2 (3 + 3).
  • coins = [1, 5, 10, 25], amount = 30 → 2 (25 + 5); greedy works.
  • coins = [1, 5, 10, 25], amount = 41 → 4 (25 + 10 + 5 + 1); greedy works.
  • coins = [2], amount = 3 → -1.
  • coins = [1], amount = 0 → 0.
  • coins = [186, 419, 83, 408], amount = 6249 → 20 (random hostile case).

The Greedy Hypothesis (And Why It Fails)

The natural greedy: sort denominations descending, take the largest that fits, recurse on the remainder.

def coin_change_greedy_WRONG(coins, amount):
    coins = sorted(coins, reverse=True)
    count = 0
    for c in coins:
        while amount >= c:
            amount -= c
            count += 1
    return count if amount == 0 else -1

Run this on coins = [1, 3, 4], amount = 6:

  1. Pick 4: amount = 2, count = 1.
  2. Pick 3? No, 2 < 3. Skip.
  3. Pick 1: twice. amount = 0, count = 3.

Result: 3 coins. Optimum: 3 + 3 = 2 coins. Greedy is wrong.

Why? The greedy choice property does not hold: taking the largest coin (4) at step 1 forces a residual problem (amount = 2) where the available coins ([1, 3, 4]) cannot reach 2 with fewer than 2 coins (1 + 1). But not taking 4 leaves us with amount = 6 and the optimal residual 3 + 3 = 2 coins. The local optimum (largest fits) is not the global optimum.

The exchange-argument failure at this concrete level:

  • Greedy picks coin 4 first. Optimal picks 3 first.
  • Try to exchange the optimal’s first 3 with greedy’s 4: residual amount becomes 6 - 4 = 2, which cannot be made with one more coin of denomination ≥ 3. So the swap breaks feasibility / minimality.
  • The exchange argument fails. Therefore the greedy is not provably optimal — and indeed isn’t.

DP Fallback (The Correct Algorithm)

def coin_change_dp(coins, amount):
    INF = float('inf')
    dp = [0] + [INF] * amount
    for w in range(1, amount + 1):
        for c in coins:
            if c <= w and dp[w - c] + 1 < dp[w]:
                dp[w] = dp[w - c] + 1
    return dp[amount] if dp[amount] != INF else -1

This is unbounded knapsack — see Phase 5 Lab 04 — Unbounded Knapsack (Coin Change) for the full derivation.

Complexity: O(amount * |coins|) time, O(amount) space.

When Does Greedy WORK On Coin Change?

Greedy is optimal on a coin system iff it is canonical — a property that depends on the specific denominations. Sufficient conditions:

  • [1, c, c², c³, …] (powers of a fixed base) — always canonical.
  • [1, 5, 10, 25, 50, 100] (US currency) — canonical.
  • [1, 2, 5, 10, 20, 50] (euro) — canonical.

Necessary and sufficient condition: the set is canonical iff for every amount m in the range [c_{k+1} + 1, c_{k+1} + c_k - 1] (where c_k is the k-th denomination from largest), the greedy answer matches the optimal. Verifying this requires checking O(c_max²) amounts — feasible for small denomination sets.

For interview purposes: never assume canonicity unless the problem explicitly states the denominations are canonical (e.g., “US currency” with the standard set). Default to DP.

A Glance At Matroid Theory (Why Some Greedy Problems Work)

A matroid M = (E, I) is a pair where E is a set of elements and I ⊆ 2^E is a family of “independent sets” satisfying:

  1. Hereditary: if A ∈ I and B ⊆ A, then B ∈ I.
  2. Exchange property: if A, B ∈ I and |A| < |B|, then there exists b ∈ B \ A such that A ∪ {b} ∈ I.

Theorem (Edmonds–Rado): the greedy algorithm produces a maximum-weight independent set on M iff M is a matroid.

Examples of matroids: the cycle-free edge sets of a graph (graphic matroid → Kruskal works), linearly-independent subsets of vectors (linear matroid), independent sets in a uniform matroid.

Coin change is not a matroid problem — there is no natural matroid structure under which “fewest coins to reach amount” is a max-weight independent set, which is why greedy doesn’t work for arbitrary denominations. Interval scheduling is effectively a matroid problem (the set of compatible activities forms an “interval matroid”), which is why earliest-end-time greedy works.

You don’t need to memorize matroid theory for interviews. You do need to know the empirical signal: if greedy doesn’t pass the counterexample stress test, fall back to DP without panic.

Decision Recipe (The Whole Point Of This Lab)

For any optimization problem that “looks greedy”:

  1. Hypothesize a greedy choice (e.g., largest first, smallest first, by ratio).
  2. Run it on a hand-crafted small input of size 4–6 with adversarial denominations / weights.
  3. Compare to brute force (recursive enumeration of all choices).
  4. If greedy ≠ brute force on any input → fall back to DP, no further deliberation.
  5. If greedy = brute force on all stress tests → try to prove via exchange argument.
    • If exchange argument works → ship greedy.
    • If exchange argument fails or is unclear → fall back to DP. Better safe than sorry under interview time pressure.

The discipline: greedy is opt-in, requires positive proof. DP is the default for optimization problems unless greedy is clearly justified.

Tests

def test_coin_change_dp():
    assert coin_change_dp([1, 3, 4], 6) == 2
    assert coin_change_dp([1, 2, 5], 11) == 3
    assert coin_change_dp([2], 3) == -1
    assert coin_change_dp([1], 0) == 0
    assert coin_change_dp([1, 5, 10, 25], 30) == 2
    assert coin_change_dp([1, 5, 10, 25], 41) == 4
    assert coin_change_dp([186, 419, 83, 408], 6249) == 20

def test_greedy_fails_on_counterexample():
    """Document the failure for posterity."""
    assert coin_change_greedy_WRONG([1, 3, 4], 6) == 3  # WRONG; correct is 2
    assert coin_change_dp([1, 3, 4], 6) == 2            # Right answer

def test_greedy_works_on_canonical():
    assert coin_change_greedy_WRONG([1, 5, 10, 25], 30) == 2
    assert coin_change_greedy_WRONG([1, 5, 10, 25], 41) == 4

Correctness Argument (For DP)

DP correctness follows from optimal substructure: dp[w] = 1 + min(dp[w - c] : c ∈ coins, c ≤ w). Each dp[w] is computed from strictly smaller subproblems, so the table fills in O(amount * |coins|) time. The minimum is over all first-coin choices, exhaustively — so we never miss the optimal first choice (in contrast to greedy, which commits to one). See Phase 5 Lab 04 for the full proof.

Common Bugs (In The DP)

  • Initializing dp[0] = INF instead of 0. (dp[0] = 0 because zero amount needs zero coins.)
  • Iterating for c: for w (orderings DP) when for w: for c (combinations DP) is intended for count of orderings — not the issue for min coins, but the analogous bug appears in LC 518 (number of ways to make change).
  • Returning dp[amount] without checking INF — returns a giant number instead of -1.

Common Bugs (In The Greedy, If You Do Try It)

  • Assuming canonicity. Always test against DP on hostile cases first.
  • Forgetting to return -1 when amount is not zero at the end.
  • Treating coins = [1] as always feasible — true, but easy to forget the early return.

Mastery Criteria

  • You can deliver the [1, 3, 4] target 6 counterexample by heart, in <30 seconds, without notes.
  • You can articulate why greedy on coin change works for [1, 5, 10, 25] but fails for [1, 3, 4] — the canonicity property — in <60 seconds.
  • You can write the DP solution in <5 minutes from blank.
  • You can name three other classic problems where greedy fails but DP works (0/1 knapsack, weighted interval scheduling, longest path in a general graph).
  • When proposing a greedy solution to any problem in mock interviews, you stress-test it against brute force on small adversarial inputs before writing production code.

← Lab 05 — Huffman Coding · Phase 6 README