Greedy vs Dynamic Programming
Greedy when you can argue that the locally best choice is part of some optimal solution. Dynamic programming when you cannot, which is most of the time. If you are unsure, DP is the safe answer, because it is correct wherever greedy is and in many places greedy is not.
Greedy commits. It makes the choice that looks best right now and never revisits it, which is why it is fast and why it is so often wrong. Dynamic programming keeps every choice open by solving each subproblem once and combining the results. The entire question is whether the problem has the property that lets greedy work, and interviewers ask this comparison to see whether you check that or assume it.
Side by side
| Dimension | Greedy | Dynamic Programming |
|---|---|---|
| Choice | Locally best, never revisited | All of them, results reused |
| Typical time | O(n log n), dominated by a sort | O(states times transitions) |
| Space | O(1) beyond the input | O(states) |
| Correctness rests on | An exchange argument | Optimal substructure alone |
| When it fails | Silently, with a plausible wrong answer | Rarely, but can be too slow or too large |
| Fractional knapsack | Correct | Unnecessary |
| 0/1 knapsack | Wrong | Correct |
When to pick each
Greedy
- Interval scheduling, where taking the earliest finishing activity provably leaves the most room.
- Huffman coding, where merging the two rarest symbols is always safe.
- Minimum spanning trees, where both Kruskal and Prim are greedy and provably correct.
- Anything where you can state an exchange argument: given an optimal solution not containing your choice, you can swap your choice in without making it worse.
Dynamic Programming
- 0/1 knapsack, where taking the densest item first can leave a gap nothing fills.
- Coin change with arbitrary denominations, where taking the largest coin first fails on inputs like 6 from coins of 1, 3 and 4.
- Edit distance, longest common subsequence, and anything comparing two sequences.
- Any problem where a choice constrains later choices in a way you cannot bound.
Testing greedy on a few examples, watching it pass, and shipping it. Greedy failures are not loud. Coin change with coins of 1, 3 and 4 making 6 returns three coins greedily, taking 4 then 1 then 1, when two threes is correct. That input looks like every other input, which is exactly why the argument matters more than the testing.
Questions people ask
How do I know if greedy works?
Try to state an exchange argument. Take any optimal solution that does not include your greedy choice, and show you can substitute the greedy choice in without making the solution worse. If you cannot construct that, assume greedy is wrong.
Why is greedy correct for fractional knapsack but not 0/1?
Because you can cut an item. Filling the remaining capacity with the densest thing available is always at least as good when partial amounts are allowed. Once items are indivisible, taking the densest first can leave capacity that nothing fits into.
Is Dijkstra greedy or DP?
It is usually described as greedy, since it permanently settles the nearest unvisited node and never reconsiders. That commitment is exactly why it breaks on negative edges, where a later cheaper route can undercut a node already settled.