A greedy algorithm builds a solution piece by piece, always making the choice that looks best right now — never reconsidering earlier decisions. When it works, it is dramatically simpler than DP. When it doesn’t, it can produce arbitrarily bad answers.
The Greedy Choice Property
For a greedy algorithm to be correct, the problem must have the greedy choice property: there is always an optimal solution that includes the locally optimal first choice. Combined with optimal substructure (the rest of the problem after a greedy choice is a smaller instance of the same kind), this justifies the approach by induction.
Classic greedy successes:
- Activity Selection — always pick the activity that finishes earliest.
- Fractional Knapsack — always take the highest value/weight ratio.
- Huffman Coding — always merge the two lowest-frequency nodes.
- Prim’s / Kruskal’s MST — always add the cheapest safe edge (cut property).
- Dijkstra’s — always relax through the closest unvisited node.
Proving Greedy Is Correct
The standard proof tool is the exchange argument: take any optimal solution and show you can swap in your greedy choice without making it worse. If the swap can be repeated, there is an optimal solution containing every greedy choice.
A second tool is the matroid: when the problem’s feasible sets form a matroid, the greedy algorithm is provably optimal. MST (graphic matroid) is the canonical example.
When Greedy Fails
Greedy is not universal. The failure mode is when local choices block future, better combinations:
- 0/1 Knapsack — taking the best-ratio item first can consume capacity needed by a higher-value pair.
- Coin Change with arbitrary denominations — always taking the largest coin can overshoot the true minimum.
- Traveling Salesman — nearest-neighbor tours can be far from optimal.
The pattern: greedy fails when the problem needs lookahead — when the value of a choice depends on which other choices remain.
Greedy vs DP
| Aspect | Greedy | Dynamic Programming |
|---|---|---|
| Decision | One locally best choice | Explores all choices |
| Reconsidering | Never | Yes, via table states |
| Correctness proof | Exchange argument | Induction on subproblems |
| Speed | Often just a sort + scan | Polynomial in the state space |
If you suspect greedy, first prove (or test) the greedy choice property. When in doubt, DP is the safe fallback that always explores the full space.
Practice Trajectory
Start with interval problems (activity selection, minimum platforms), then ratio problems (fractional knapsack, optimal merge patterns), then graph algorithms (Prim, Kruskal, Dijkstra), and finally matroid-flavored problems. For every problem, ask: “can a locally optimal choice ever block the global optimum?”