Greedy algorithms commit to a locally attractive choice. Dynamic programming keeps alternatives alive through reusable subproblems. The difference is whether an early decision can safely become irreversible.
What a greedy proof needs
A plausible rule is not enough. Show that an optimal solution can be transformed to include the greedy choice without becoming worse, or show that the choice always stays ahead of every competitor. Interval scheduling works because selecting the earliest finishing compatible interval leaves maximal room for what follows.
When dynamic programming is safer
If a locally good decision changes which future options remain, and no exchange argument protects it, model the alternatives. Knapsack-style problems are classic examples: the highest value or best value-per-weight item can block a better combination.
Use counterexamples early
Try to break a proposed greedy rule with the smallest instance you can invent. Counterexamples expose hidden interactions quickly. If the rule survives, articulate the invariant; if it fails, identify the state needed to represent the unresolved choices.
Continue with the book
Explore the full treatment, worked examples, and exercises in Algorithmic Edge.
Adapted from Algorithmic Edge, published by Choral Software. Article text and original examples © 2026 Choral Software. All rights reserved.