When Does Greedy Work? Greedy vs Dynamic Programming

A greedy algorithm is only as good as its proof. Greedy works when a problem has the greedy-choice property — the locally best move is always part of some optimal solution. When that fails, greedy quietly returns wrong answers on certain inputs, and you need dynamic programming instead. This page shows how to prove greedy is correct, how to disprove it with a counterexample, and how to decide between greedy and DP.

Greedy vs dynamic programming

Both strategies need optimal substructure (an optimal answer is built from optimal sub-answers). The difference is when the choice happens:

The rule of thumb: try greedy first because it is cheap, but only ship it if you can prove it. If you cannot prove the greedy-choice property, fall back to DP, which is always safe for problems with optimal substructure.

The counterexample test (disproving greedy)

The fastest way to kill a greedy idea is to find one input where it loses. Classic case: coin change with a non-canonical coin set. The greedy “take the largest coin that fits” gives the minimum number of coins for normal currencies — but not for arbitrary denominations.

With coins {1, 3, 4} and amount 6:

• Greedy: take 4, then 1, then 1 → 3 coins.
• Optimal: 3 + 3 → 2 coins.

Here is the greedy coin-change next to the correct DP, so you can see the divergence:

#include <vector>
#include <algorithm>
#include <climits>

int greedyCoins(int amount, std::vector<int> coins) { // sorted descending
    int count = 0;
    for (int c : coins) { count += amount / c; amount %= c; }
    return amount == 0 ? count : -1; // may be wrong / fail to make change
}

int dpCoins(int amount, const std::vector<int>& coins) { // always correct
    std::vector<int> best(amount + 1, INT_MAX);
    best[0] = 0;
    for (int a = 1; a <= amount; a++)
        for (int c : coins)
            if (c <= a && best[a - c] != INT_MAX)
                best[a] = std::min(best[a], best[a - c] + 1);
    return best[amount] == INT_MAX ? -1 : best[amount];
}

int greedyCoins(int amount, int[] coins) { // sorted descending
    int count = 0;
    for (int c : coins) { count += amount / c; amount %= c; }
    return amount == 0 ? count : -1; // may be wrong / fail to make change
}

int dpCoins(int amount, int[] coins) { // always correct
    int[] best = new int[amount + 1];
    java.util.Arrays.fill(best, Integer.MAX_VALUE);
    best[0] = 0;
    for (int a = 1; a <= amount; a++)
        for (int c : coins)
            if (c <= a && best[a - c] != Integer.MAX_VALUE)
                best[a] = Math.min(best[a], best[a - c] + 1);
    return best[amount] == Integer.MAX_VALUE ? -1 : best[amount];
}

function greedyCoins(amount, coins) { // sorted descending
  let count = 0;
  for (const c of coins) { count += Math.floor(amount / c); amount %= c; }
  return amount === 0 ? count : -1; // may be wrong / fail to make change
}

function dpCoins(amount, coins) { // always correct
  const best = new Array(amount + 1).fill(Infinity);
  best[0] = 0;
  for (let a = 1; a <= amount; a++)
    for (const c of coins)
      if (c <= a && best[a - c] !== Infinity)
        best[a] = Math.min(best[a], best[a - c] + 1);
  return best[amount] === Infinity ? -1 : best[amount];
}

def greedy_coins(amount, coins):  # sorted descending
    count = 0
    for c in coins:
        count += amount // c
        amount %= c
    return count if amount == 0 else -1  # may be wrong / fail

def dp_coins(amount, coins):  # always correct
    best = [float("inf")] * (amount + 1)
    best[0] = 0
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a and best[a - c] != float("inf"):
                best[a] = min(best[a], best[a - c] + 1)
    return best[amount] if best[amount] != float("inf") else -1

For beginners: To disprove a greedy idea you only need one failing input. Try tiny, awkward cases by hand — odd coin sets, ties, items where “biggest” and “best ratio” disagree. If greedy and brute force ever differ, greedy is out.

The exchange argument (proving greedy)

When you can’t break greedy, you prove it correct — usually with an exchange argument:

1. Take any optimal solution O.
2. Show that you can swap one of its choices for the greedy choice without making O worse (and without breaking feasibility).
3. Repeat the swap; O is transformed step by step into the greedy solution while staying optimal.
4. Therefore the greedy solution is also optimal.

The activity selection proof is the textbook example: replace the first activity in any optimal schedule with the one that finishes earliest, and you never lose a slot — so “earliest finish time” is safe.

A second style is the “greedy stays ahead” argument: prove that after each step, the greedy partial solution is at least as good (e.g. has finished at least as many activities) as any other partial solution.

A practical decision checklist

When you suspect greedy:

1. Name the selection rule. What does “best right now” mean exactly?
2. Hunt for a counterexample. Small, adversarial inputs first.
3. If none, attempt an exchange argument. Can the greedy choice always replace an optimal one safely?
4. Still unsure? Use DP. It is always correct given optimal substructure; only fall back to greedy when proven.

Going deeper: Problems where greedy is proven correct include activity selection, Huffman coding, fractional knapsack, Dijkstra, and minimum spanning trees. Problems where it fails include 0/1 knapsack, general coin change, and longest path — all of which need DP.

Pitfall: “It passed my three test cases” is not a proof. Greedy bugs hide in inputs with ties or where two reasonable selection rules disagree. Prove it or use DP.

Next: a fully proven greedy algorithm — activity selection.