Skip to main content
PreparationZone Logo
PreparationZone
Back to Fundamentals

Fundamentals · Hard · Free

When is greedy correct vs when you need dynamic programming?

FresherFundamentalsData Structures & Algorithms
Model answer

Greedy vs DP

GreedyDP
ChoiceLocal optimum each stepTry all sub-states
ProofNeed exchange argumentRecurrence + memo
ExampleActivity selection, HuffmanCoin 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.