Fundamentals · Hard · Free
When is greedy correct vs when you need dynamic programming?
FresherFundamentalsData Structures & Algorithms
Greedy vs DP
| Greedy | DP | |
|---|---|---|
| Choice | Local optimum each step | Try all sub-states |
| Proof | Need exchange argument | Recurrence + memo |
| Example | Activity selection, Huffman | Coin change, knapsack |
Greedy fails when local choice blocks global optimum—then DP.
java
// Greedy activity selection (by finish time) — O(n log n)
activities.sort(Comparator.comparingInt(a -> a.end));
int count = 0, lastEnd = 0;
for (Activity a : activities) {
if (a.start >= lastEnd) { count++; lastEnd = a.end; }
}Classic failed greedy: arbitrary coin denominations for min coins.