When Greedy Fails: Greedy vs DP

A greedy algorithm builds a solution one step at a time, always taking whichever choice looks best right now, and it never reconsiders that choice later. Sometimes that happens to produce the true optimal answer — but sometimes an early, obviously-good-looking choice quietly blocks a better solution further down the line, and the algorithm ends up wrong without any warning. Dynamic programming (DP) is the fix: instead of committing to one choice, it methodically explores the relevant choices for every sub-problem and remembers the best outcome, so it can never be fooled by a locally attractive but globally wrong move. This lesson is about learning to tell the two situations apart, using coin change and 0/1 knapsack as classic cases where greedy fails, and activity selection as a case where greedy is provably correct.

Overview: Greedy-Choice Property vs Optimal Substructure

Every problem that DP can solve has optimal substructure: the optimal solution to the whole problem is built from optimal solutions to its sub-problems. Greedy algorithms also rely on optimal substructure, but they additionally require something stronger — the greedy-choice property: making the locally best choice at each step, and never revisiting it, still leads to a globally optimal solution overall. When a problem has both properties, greedy isn’t just faster than DP, it’s the correct, provably optimal approach. This is usually established with an "exchange argument": assume some optimal solution disagrees with the greedy choice, then show you can swap the greedy choice into that solution without making it any worse. When a problem has optimal substructure but not the greedy-choice property, greedy still runs and still returns an answer — it just might be the wrong one, and it gives you no signal that anything went wrong.

Concretely: suppose you’re making 6 cents of change using coins worth 4, 3, and 1 cent. A greedy cashier grabs the largest coin that still fits at every step: a 4-cent coin (2 cents left), then two 1-cent coins — 3 coins total. But 3 + 3 = 6 uses only 2 coins. The greedy rule "always take the biggest coin you can" sounds reasonable but is wrong here, because spending the 4-cent coin used up value in a way the remaining denominations couldn’t recover efficiently. DP avoids this by computing, for every amount from 0 up to the target, the true minimum coin count using only already-solved smaller amounts, so it never has to guess.

This gap between "looks locally optimal" and "is globally optimal" is the entire lesson. Some classic problems — activity/interval scheduling, Huffman coding, Kruskal’s and Prim’s minimum spanning tree, Dijkstra’s shortest path with non-negative edge weights, the fractional knapsack problem — have a provable greedy-choice property, so greedy is the textbook-correct, efficient solution. Others — 0/1 knapsack, coin change with arbitrary denominations, longest common subsequence, longest increasing subsequence — do not, and applying greedy to them is a bug, not an optimization.

Time and Space Complexity

Complexity depends on the specific problem pair, but a pattern holds across almost every greedy-vs-DP comparison: greedy is asymptotically cheaper, and DP is asymptotically more thorough. Greedy typically needs one sort (O(n log n)) followed by a single linear pass (O(n)). DP typically fills a table indexed by sub-problem size: for coin change that’s O(amount) states, each doing O(k) work for k denominations, giving O(amount · k) time and O(amount) space; for 0/1 knapsack it’s O(n · capacity) time and space, because the table has one row per item and one column per possible capacity, and each cell does O(1) work by comparing two already-computed cells.

Approach	Time	Space	Always optimal?
Greedy coin change (largest coin first)	O(amount) worst case, plus O(k log k) to sort k denominations	O(1) extra	No — only for "canonical" coin systems like most real-world currencies
DP coin change (minimum coins)	O(amount · k) for k denominations	O(amount)	Yes, always
Greedy knapsack (value/weight ratio)	O(n log n) to sort n items	O(1) extra	Only for the fractional knapsack; no for 0/1 knapsack
DP 0/1 knapsack	O(n · capacity)	O(n · capacity), reducible to O(capacity) with a rolling array	Yes, always
Greedy activity selection (earliest finish time)	O(n log n) to sort n activities	O(1) extra	Yes, always — this problem does have the greedy-choice property

Examples

Example 1: Coin Change — Greedy vs DP

The classic counterexample uses coins worth 4, 3, and 1 to make 6 cents of change. A greedy strategy grabs the biggest coin that still fits at each step:

def greedy_coin_change(coins: list[int], amount: int) -> list[int]:
    coins_sorted = sorted(coins, reverse=True)
    result = []
    remaining = amount
    for coin in coins_sorted:
        while remaining >= coin:
            result.append(coin)
            remaining -= coin
    return result


coins = [1, 3, 4]
amount = 6
change = greedy_coin_change(coins, amount)
print(f"Greedy picks: {change}")
print(f"Greedy coin count: {len(change)}")

Output:

Greedy picks: [4, 1, 1]
Greedy coin count: 3

Sorted descending, the coins are tried in order 4, 3, 1. The 4-cent coin fits once (6 → 2 remaining), the 3-cent coin never fits again, and the 1-cent coin is used twice (2 → 1 → 0). That’s 3 coins. Now compare a bottom-up DP solution that computes the true minimum number of coins for every amount from 0 up to 6, using only already-solved smaller amounts:

def min_coins_dp(coins: list[int], amount: int) -> int:
    INF = float("inf")
    dp = [0] + [INF] * amount
    for total in range(1, amount + 1):
        for coin in coins:
            if coin <= total and dp[total - coin] + 1 < dp[total]:
                dp[total] = dp[total - coin] + 1
    return dp[amount] if dp[amount] != INF else -1


coins = [1, 3, 4]
amount = 6
print(f"DP minimum coins: {min_coins_dp(coins, amount)}")

Output:

DP minimum coins: 2

dp[i] holds the minimum coins needed to make amount i. Building it up: dp[3] becomes 1 (a single 3-cent coin), and dp[6] can then be reached as dp[3] + 1 using another 3-cent coin, giving 2 total — better than anything greedy found, because DP considered the option of using two 3-cent coins instead of committing to the 4-cent coin first.

Example 2: 0/1 Knapsack — Greedy vs DP

Three items with (weight, value) pairs (10, 60), (20, 100), (30, 120) and a knapsack capacity of 50. A common greedy heuristic sorts items by value-per-weight ratio and takes whichever still fits:

def greedy_knapsack(weights: list[int], values: list[int], capacity: int) -> int:
    items = sorted(zip(weights, values), key=lambda item: item[1] / item[0], reverse=True)
    total_value = 0
    remaining_capacity = capacity
    for weight, value in items:
        if weight <= remaining_capacity:
            remaining_capacity -= weight
            total_value += value
    return total_value


weights = [10, 20, 30]
values = [60, 100, 120]
capacity = 50
print(f"Greedy total value: {greedy_knapsack(weights, values, capacity)}")

Output:

Greedy total value: 160

Ratios are 6.0, 5.0, and 4.0, so greedy takes item (10, 60) first (40 capacity left), then item (20, 100) (20 capacity left), then can’t fit item (30, 120) — total value 160. Now the DP solution, which considers, for every item and every possible capacity, whether including that item beats excluding it:

def knapsack_dp(weights: list[int], values: list[int], capacity: int) -> int:
    n = len(weights)
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        weight, value = weights[i - 1], values[i - 1]
        for cap in range(capacity + 1):
            dp[i][cap] = dp[i - 1][cap]
            if weight <= cap:
                dp[i][cap] = max(dp[i][cap], dp[i - 1][cap - weight] + value)
    return dp[n][capacity]


weights = [10, 20, 30]
values = [60, 100, 120]
capacity = 50
print(f"DP optimal value: {knapsack_dp(weights, values, capacity)}")

Output:

DP optimal value: 220

DP finds that skipping the first item entirely and taking items (20, 100) and (30, 120) uses exactly 50 capacity for 220 value — 60 more than greedy found. Greedy’s early, irrevocable choice to take item (10, 60) permanently used up capacity that the optimal solution needed for a better combination. Note that this same ratio-greedy strategy is provably optimal for the fractional knapsack, where you’re allowed to take part of an item — the greedy-choice property holds there because you can always top off remaining capacity with a fraction of the next-best item, but 0/1 knapsack’s all-or-nothing constraint breaks that property.

Example 3: Activity Selection — Where Greedy Succeeds

Not every greedy strategy is broken. Given a set of activities with start and finish times, choosing the maximum number of non-overlapping activities is solved optimally by always picking the activity that finishes earliest among those that don’t conflict with what’s already chosen:

def max_activities(start: list[int], finish: list[int]) -> list[int]:
    order = sorted(range(len(start)), key=lambda i: finish[i])
    selected = [order[0]]
    last_finish = finish[order[0]]
    for i in order[1:]:
        if start[i] >= last_finish:
            selected.append(i)
            last_finish = finish[i]
    return selected


start = [1, 3, 0, 5, 8, 5]
finish = [2, 4, 6, 7, 9, 9]
chosen = max_activities(start, finish)
print(f"Selected activity indices: {chosen}")
print(f"Number of activities: {len(chosen)}")

Output:

Selected activity indices: [0, 1, 3, 4]
Number of activities: 4

Sorted by finish time the order is already 0, 1, 2, 3, 4, 5. Activity 0 (1–2) is taken first. Activity 1 (3–4) starts after activity 0 finishes, so it’s taken. Activity 2 (0–6) starts before activity 1 finishes, so it’s skipped. Activity 3 (5–7) starts after activity 1 finishes, so it’s taken. Activity 4 (8–9) starts after activity 3 finishes, so it’s taken. Activity 5 (5–9) starts before activity 4 finishes, so it’s skipped. Four activities selected, and this is provably the maximum possible: if any optimal solution didn’t pick the earliest-finishing activity first, you could always swap it in without shrinking the count, since finishing earlier can only leave more room for what comes after. That’s the exchange argument that makes this greedy strategy correct, in contrast to knapsack and coin change.

How It Works Step by Step

To see exactly why DP outperforms greedy on coin change, trace the dp array being built for coins [4, 3, 1] and amount 6, where dp[i] is the minimum coins needed for amount i:

• dp[0] = 0 (base case: zero coins needed for zero amount).
• dp[1]: only the 1-cent coin fits; dp[0] + 1 = 1.
• dp[2]: only the 1-cent coin fits; dp[1] + 1 = 2.
• dp[3]: the 1-cent coin gives dp[2] + 1 = 3, but the 3-cent coin gives dp[0] + 1 = 1, which is smaller, so dp[3] = 1.
• dp[4]: the 4-cent coin gives dp[0] + 1 = 1, the smallest option, so dp[4] = 1.
• dp[5]: best option is the 4-cent coin plus dp[1], or the 3-cent coin plus dp[2]; both give 2, so dp[5] = 2.
• dp[6]: the 3-cent coin gives dp[3] + 1 = 2, which beats the 4-cent coin’s dp[2] + 1 = 3, so dp[6] = 2.

Notice that DP never "decided" to avoid the 4-cent coin — it computed the cost of every option at every step and kept the best one. Greedy, by contrast, took the 4-cent coin at amount 6 without ever checking whether a different first coin would leave a cheaper remainder. That single irreversible decision is exactly where greedy diverges from optimal.

Common Mistakes

Mistake 1: Trusting greedy on an unproven problem

It’s tempting to assume that "take the biggest piece first" is always a safe strategy for a minimization problem. It is not, unless the coin denominations happen to form a canonical system (most real-world currencies do, but arbitrary denominations often don’t):

def coin_count_wrong(coins: list[int], amount: int) -> int:
    coins.sort(reverse=True)
    count = 0
    remaining = amount
    for coin in coins:
        count += remaining // coin
        remaining %= coin
    return count  # WRONG: assumes greedy is always minimal -- it isn't for [4, 3, 1], amount 6

Output:

(Not executed -- demonstrates a flawed assumption. For coins=[4, 3, 1], amount=6 this returns 3, but the true minimum is 2.)

The fix is to compute the answer with DP instead of assuming greedy is correct:

def coin_count_correct(coins: list[int], amount: int) -> int:
    INF = float("inf")
    dp = [0] + [INF] * amount
    for total in range(1, amount + 1):
        for coin in coins:
            if coin <= total and dp[total - coin] + 1 < dp[total]:
                dp[total] = dp[total - coin] + 1
    return dp[amount] if dp[amount] != INF else -1


coins = [4, 3, 1]
amount = 6
print(f"Correct minimum coins: {coin_count_correct(coins, amount)}")

Output:

Correct minimum coins: 2

Mistake 2: Mutable default argument in a memoized DP helper

DP is often written top-down with recursion plus a memo cache. A very common Python bug is initializing that cache as a mutable default argument:

def min_coins_memo_wrong(coins: list[int], amount: int, memo={}) -> int:
    if amount == 0:
        return 0
    if amount in memo:
        return memo[amount]
    best = float("inf")
    for coin in coins:
        if coin <= amount:
            best = min(best, min_coins_memo_wrong(coins, amount - coin, memo) + 1)
    memo[amount] = best
    return best

Output:

(Not executed -- demonstrates the mutable-default-argument bug: memo={} is created once at function-definition time and silently reused across every call, so a later call with a different coins list can read stale results left over from an earlier call.)

Default argument values are evaluated exactly once, when the function is defined — not once per call — so every call that doesn’t explicitly pass memo shares the exact same dictionary. Call the function once with coins=[4, 3, 1] and again later with a different coin set, and the second call can silently reuse cached results computed for the first set of coins. The fix is to default to None and create a fresh dictionary inside the function body:

def min_coins_memo_correct(coins: list[int], amount: int, memo: dict[int, int] | None = None) -> int:
    if memo is None:
        memo = {}
    if amount == 0:
        return 0
    if amount in memo:
        return memo[amount]
    best = float("inf")
    for coin in coins:
        if coin <= amount:
            best = min(best, min_coins_memo_correct(coins, amount - coin, memo) + 1)
    memo[amount] = best
    return best


coins = [4, 3, 1]
amount = 6
print(f"Memoized minimum coins: {min_coins_memo_correct(coins, amount)}")

Output:

Memoized minimum coins: 2

Best Practices

• Only trust greedy when you can state (or recall) the exchange argument proving the greedy-choice property; if you can’t articulate why the locally best choice can never be beaten later, default to DP.
• For coin systems, don’t assume greedy works just because it works for familiar currencies — verify the denominations are canonical, or fall back to DP for a guaranteed-correct answer.
• Recognize the knapsack family by constraint: if items are divisible (fractional knapsack), greedy by value/weight ratio is optimal; if items are all-or-nothing (0/1 knapsack), you need DP.
• In interviews, if you reach for a greedy solution, say out loud why it’s correct (or test it against a brute-force/DP solution on a small example) before committing to it — interviewers often plant exactly the coin-change or knapsack counterexample to see if you notice.
• Never default a memoization cache to a mutable object ({} or []); default to None and initialize inside the function.
• When both greedy and DP are candidates and you’re unsure which applies, implement DP first for correctness, then consider whether a proven greedy-choice property lets you simplify to a faster greedy pass.

Practice Exercises

1. Using coins [1, 5, 7] and amount 10, trace the largest-coin-first greedy strategy by hand and count the coins it uses. Then think about (or code) the DP minimum. Hint: greedy will not find the 2-coin solution.
2. For items with weights [5, 4, 6, 3] and values [10, 40, 30, 50] and capacity 10, run both the ratio-greedy knapsack and the DP knapsack from this lesson. Do they agree on this particular input? If so, explain why that agreement doesn’t mean greedy is safe to use on 0/1 knapsack problems in general.
3. Without writing code, sketch the exchange argument for why choosing the earliest-finishing activity first is optimal for activity selection. (Hint: consider an optimal solution that picks some other activity first, and show you can always replace it with the earliest-finishing one without reducing the total count.)

Summary

• Greedy makes one irrevocable, locally-best choice per step; DP explores the relevant choices for every sub-problem and remembers the best result, so it can’t be misled by an early choice that looks good but blocks a better outcome later.
• Greedy is correct only when a problem has the greedy-choice property (provable via an exchange argument) in addition to optimal substructure — DP only requires optimal substructure.
• Coin change with arbitrary denominations and 0/1 knapsack are classic examples where greedy fails; DP guarantees the optimal answer in O(amount · k) and O(n · capacity) time respectively.
• Fractional knapsack and activity selection are classic examples where the same kind of greedy strategy is provably optimal — the difference is entirely in the problem’s structure, not the greedy technique itself.
• When unsure, default to DP for correctness; only switch to greedy once you can justify why the locally best choice can never be beaten later.
• Avoid two Python-specific traps highlighted here: never assume greedy is correct without proof, and never use a mutable default argument ({}) for a memoization cache.