Skip to main content

Greedy Versus DP: When Each Is Justified

What This Concept Is​

Greedy and DP both rely on optimal substructure. They differ on how many candidate choices you must evaluate per state:

  • Greedy. At each step, one specific local choice is provably part of some optimal solution. You commit and never reconsider. Runtime is typically $O(n \log n)$ (dominated by sorting) or better.
  • DP. You cannot commit to a single local choice, so you try all of them, reuse subproblem answers, and take the best. Runtime is (states) $\times$ (choices per state).

If you can prove a greedy-choice property (via exchange argument, matroid structure, or similar - concept 10), use greedy. Otherwise, fall back to DP.

A compact way to see the difference: greedy solves $OPT(x) = \text{fixed-choice}(OPT(x'))$, where the choice is determined by the input. DP solves $OPT(x) = \text{best of} {OPT(x_1), OPT(x_2), \ldots}$, where the choice requires evaluation.

Matroids (CLRS) and exchange arguments (concept 10) are the formal reasons some problems admit greedy; absence of these is the signal to write a DP.

Why It Matters Here​

Confusing the two is the most common paradigm error in the module. A "greedy" that works on the samples but fails on adversarial input is a silent bug; a DP used where a greedy exists is correct but slower and more code. The question "greedy or DP?" has to be answered with a proof, not a vibe.

In interviews and on contests, a disproportionate fraction of incorrect solutions arise from applying a greedy rule that happens to work on the examples but fails on one carefully chosen case. In production, the pattern is the same: a developer encodes a policy as "take the cheapest option first" and ships a subtly incorrect routing algorithm.

Concrete Example​

Example 1 (fractional knapsack - greedy works). Items have weight $w_i$ and value $v_i$; you can take fractions. Capacity $W$.

Greedy rule: sort by $v_i / w_i$ descending, take as much as capacity permits.

Exchange proof. In any optimal solution, if some high-ratio item is not fully taken while a lower-ratio item is partially taken, swap a unit of weight between them. The total value cannot decrease (higher ratio replacing lower ratio). Iterate until the solution is greedy-like. Runtime $\Theta(n \log n)$.

Example 2 ($0/1$ knapsack - greedy fails, DP works). Same items, but each is taken whole or not at all. Consider items $(w, v) = (1, 60), (2, 100), (3, 120)$, capacity $W = 5$.

  • Greedy by ratio: item 1 (ratio 60), then item 2 (ratio 50). Total weight 3, value 160. Capacity remaining 2, item 3 too heavy. Result: 160.
  • Optimal: items 2 and 3, weight 5, value 220.

The $0/1$ constraint breaks the greedy-choice property because committing to item 1 locks out the strictly better combination. DP over $(i, w)$ = (item index, remaining capacity) solves it in $\Theta(nW)$.

Example 3 (activity selection vs weighted interval scheduling).

  • Unweighted activity selection. Greedy (earliest finish time) works, proved by exchange. $O(n \log n)$.
  • Weighted version. Each activity has a value $v_i$. Greedy by any obvious rule (earliest finish, highest value, highest $v/d$) fails. DP: sort by finish time, let $p(i)$ = largest $j < i$ compatible with $i$; then $OPT(i) = \max(OPT(i-1), v_i + OPT(p(i)))$. $O(n \log n)$ with binary search for $p$.

Same input shape, different answer paradigm. The value weights introduce a trade-off a single local choice cannot see.

Example 4 (coin change).

  • Canonical US denominations ${1, 5, 10, 25}$: greedy (largest-first) works.
  • Adversarial denominations ${1, 3, 4}$, target 6: greedy takes $4 + 1 + 1 = 3$ coins, optimal is $3 + 3 = 2$ coins. Greedy fails; DP is required for arbitrary denominations.

Example 5 (MST). Kruskal's and Prim's are both greedy; correctness follows from the matroid structure of graphic matroids. Both run in $O(m \log m)$.

Common Confusion / Misconceptions​

  • "Greedy is always faster, DP is always slower." True asymptotically, but DP is correct on more problems. Speed does not help if the answer is wrong.
  • "If greedy gives the right answer on my samples, it must be optimal." Sample sets almost never include the adversarial inputs that break plausible greedy rules. Either prove the exchange or use DP.
  • "$0/1$ knapsack is always DP." Small cases ($n \le 30$) can be solved by meet-in-the-middle in $O(2^{n/2})$; some structured variants (items with special weight patterns) have greedy solutions; fully polynomial approximation schemes exist. Paradigm choice depends on constraints.
  • "Greedy-choice property = optimal substructure." Both greedy and DP use optimal substructure. The additional property greedy needs is that the locally optimal choice is globally safe.
  • "Sorting by a clever key turns any problem into greedy." Sorting is often the mechanism by which a greedy rule is applied, but the rule's correctness still requires an exchange argument. Sorting by $v/w$ does not make $0/1$ knapsack greedy; it just helps enumerate items in a useful order.
  • "If DP works, don't bother with greedy." The $O(n \log n)$ greedy versus $O(n W)$ DP on fractional vs $0/1$ knapsack is a factor of up to $W$ in runtime; for $W = 10^6$, this is the difference between instant and unusable.

How To Use It​

Decision procedure for a new optimization problem:

  1. Propose a greedy rule. Write it in one sentence.
  2. Try to prove it by exchange argument. Given an optimal OPT, swap your greedy choice in without loss.
  3. If the proof sticks, implement greedy. Sort-then-scan pattern; $O(n \log n)$ typical.
  4. If the proof fails, find the smallest adversarial input (a counterexample). Its shape tells you which trade-off the greedy misses.
  5. Define a DP state that captures that trade-off (often "index, remaining resource, last choice").
  6. Write the recurrence (concept 12), implement (concept 13), stress-test against brute force (concept 15).
  7. Document both paradigms in your design doc: why greedy was ruled out, why DP's state is what it is. That note is the ADR for your algorithmic decision.

Transfer / Where This Shows Up Later​

  • S1 M5 (problem solving) taught "commit or explore." Greedy is commit; DP is explore + remember.
  • S4 (systems) uses greedy register allocation (graph coloring heuristic) where DP would be overkill, and DP instruction scheduling where the local choice cannot see the global trade-off.
  • S5 (OS) runs greedy EDF scheduling (optimal for preemptive single-processor); multiprocessor scheduling becomes DP or NP-hard.
  • S6 (databases) uses greedy join-order heuristics (left-deep trees) at the outer level and DP within each subplan (Selinger's system R optimizer).
  • S7 (architecture) decides between greedy and DP for capacity planning: greedy "add the most overloaded shard first" versus DP over a finite horizon of traffic forecasts.
  • S8 (distributed systems) uses greedy load-balancing at the edge (consistent hashing plus round-robin) and DP for offline optimal replica placement.

Concept 10 is the formal greedy theory; concept 12-13 are the DP implementation details; concept 18 integrates the two into triage.

Check Yourself​

  1. Why does the exchange argument for fractional knapsack fail in the $0/1$ case? Produce the minimal counterexample.
  2. Give two problems with identical-looking inputs where one is greedy and the other is DP.
  3. What DP state would you use for weighted interval scheduling? Why is greedy not enough?
  4. Coin change: why does greedy work for ${1, 5, 10, 25}$ but not ${1, 3, 4}$? What property do the first denominations have?
  5. Under what condition does DP reduce to greedy - i.e., what would make the per-state max trivial?

Mini Drill or Application​

Classify each problem as greedy, DP, or neither (with a reason).

  1. Minimum number of coins from ${1, 5, 10, 25}$ to make amount $T$.
  2. Minimum number of coins from ${1, 3, 4}$ to make amount $T$.
  3. Activity selection, unweighted.
  4. Activity selection, weighted (each activity has a value).
  5. Minimum spanning tree.
  6. $0/1$ knapsack.
  7. Huffman coding.
  8. Partition an array into two subsets with equal sum.
  9. Given a tree, select the largest independent set of nodes (no two adjacent selected).
  10. Implementation drill. Solve "maximum non-overlapping intervals with value $v_i$" both greedily (as a wrong attempt) and with DP. Confirm on the minimal counterexample that greedy is wrong. Stress-test DP against brute force on $n \le 14$. Complexity: DP $O(n \log n)$ after sorting by finish time, brute force $O(2^n \cdot n)$.

Read This Only If Stuck​