Greedy or dynamic programming?
“A problem looks like it could be greedy. How do you decide whether greedy is correct or whether you need DP?”
What this tests
- Whether the candidate knows greedy needs a *proof* and can sketch an exchange argument.
- Whether they actively search for counterexamples before trusting a greedy rule.
- Knowledge of the classic pairs: coin change (greedy fails for arbitrary denominations), interval scheduling (greedy works), knapsack (fractional greedy, 0/1 DP).
- Understanding that greedy is DP where only one transition ever needs to be considered.
Strong answer
Greedy is correct only if the problem has the greedy-choice property: some locally optimal choice is guaranteed to be part of *some* globally optimal solution, and after making it the remaining problem is a smaller instance of the same kind. Both greedy and DP need optimal substructure; the difference is that DP considers every choice at each state and greedy commits to one. So the question is really: can I prove that one specific choice is always safe?
The tool for that proof is the exchange argument: take any optimal solution that does not make the greedy choice, swap in the greedy choice, and show the result is no worse. In Interval Scheduling, picking the interval that ends earliest is safe because any optimal solution's first interval can be replaced by the earliest-ending one without breaking compatibility with the rest. If the exchange argument does not go through, greedy is suspect. The other tool is counterexample hunting: try small adversarial inputs. Coin Change with coins {1, 3, 4} and amount 6 — greedy gives 4+1+1, optimum is 3+3. That one example kills the greedy for arbitrary denominations, though it works for canonical systems like US coins.
A strong candidate knows the sibling pairs: Fractional Knapsack is greedy by value density, 0/1 Knapsack is not (density greedy fails when a low-density item fills the capacity exactly); Activity Selection greedy by earliest finish works, weighted interval scheduling needs DP; minimum spanning tree greedy (Kruskal's Algorithm) works because of the cut property, shortest path with negative edges does not. When unsure in an interview, they say so, write the DP (always correct if the state is right), and note that a greedy would be an optimization to prove later — that ordering is the mark of an engineer who values correctness over cleverness.
Green flags · Red flags
- Says greedy needs a proof and names the exchange argument.
- Tries a counterexample before committing, and produces the coin-change one with
{1, 3, 4}or similar. - Knows fractional vs 0/1 knapsack and why density fails for 0/1.
- Frames greedy as DP with a provably dominant transition.
- Defaults to DP when uncertain and states the tradeoff explicitly.
- Identifies the greedy criterion precisely ("earliest finish", not "shortest interval").
- Asserts a greedy is correct because "it seems right" or "it passed the examples".
- Uses "start earliest" or "shortest duration" for interval scheduling.
- Applies greedy coin change to arbitrary denominations.
- Cannot explain what would make a greedy choice unsafe.
- Thinks greedy and DP are unrelated techniques.
Follow-up questions
Each follow-up changes a requirement; the right answer changes with it.