Greedy vs Dynamic Programming

Greedy and dynamic programming both solve optimization problems by exploiting structure, but they make decisions at different times. Greedy chooses now and commits. DP delays commitment by computing the value of multiple states, then lets a recurrence decide which future is best.

A useful mental model is futures. Greedy keeps one future because a proof says all other futures are dominated or exchangeable. DP keeps many futures because early choices can become good or bad depending on later constraints. If you cannot safely discard competing futures, you should be suspicious of a greedy solution.

Greedy is usually safe when the local choice protects a bottleneck resource that every future solution needs. Earliest-ending intervals protect time. Farthest reach protects array progress. Replacing the longest job under a deadline protects total scheduled time. Choosing a character only when its future availability is safe protects string feasibility.

The key is dominance. If one choice leaves the future at least as flexible as another choice while achieving the same immediate role, the worse choice can be discarded. That is the heart of many exchange arguments and invariants.

Use DP when two choices cannot be ranked locally because their value depends on later decisions. In 0-1 Knapsack, a high-value item may consume capacity needed for a combination of smaller items. In Edit Distance, insert, delete, and replace each lead to different prefix states that must all be evaluated. In many coin systems, choosing the largest coin first can prevent the fewest total coins.

These problems still have optimal substructure, but no single first choice is provably safe across all inputs. DP keeps states such as index, capacity, amount, or two prefix lengths so that each future can be compared after its consequences are known.

Ask four questions before choosing the paradigm:

1. Can I state a local rule that chooses one action before solving the rest?
2. Can I prove an optimal solution exists that takes this action?
3. After taking it, is the remaining problem the same type with a smaller boundary?
4. If the answer to question two is no, what state variables are needed to compare the competing futures?

If the proof is strong, implement greedy. If the proof keeps breaking because different histories matter, define DP states. This diagnostic is especially valuable when a problem is disguised as sorting, scheduling, or reachability but actually requires retaining alternatives.