Greedy vs Dynamic Programming Decision
You'll learn: How to decide whether a problem calls for a greedy algorithm or dynamic programming.
When to Choose Which
You've seen both greedy algorithms (make the locally optimal choice at each step) and dynamic programming (solve overlapping subproblems). But how do you know which approach fits a problem?
Use Greedy when:
- The greedy choice property holds: making the locally optimal choice always leads to a globally optimal solution
- There's no need to reconsider past decisions
- Example: Activity Selection — once you pick the earliest-finishing activity, you never need to "undo" that choice
Use Dynamic Programming when:
- You need to explore multiple possibilities before deciding
- Later choices depend on comparing different earlier scenarios
- The greedy approach produces counterexamples (suboptimal results)
- Example: 0/1 Knapsack — taking the "best" item first might fill your bag poorly; you need to compare "take it" vs "leave it" for every item
The Litmus Test
Think of it like packing for a trip. Greedy is like grabbing clothes in order of preference until your bag is full — works if items are small and you just want maximum value. Dynamic Programming is like trying different combinations — "what if I skip this bulky jacket to fit three shirts instead?" — necessary when items have complex size/value tradeoffs.
Ask yourself: "If I make what seems like the best choice now, could I later regret it and wish I'd chosen differently?" If yes, you likely need DP. If the locally best choice is always safe, greedy works.
Key Takeaway: Choose greedy when the optimal path is built by always taking the locally best step; choose dynamic programming when you must compare multiple paths through overlapping subproblems to find the global optimum.