Why This Matters
Many optimization problems look greedy at first. The hard part is proving a local choice is always safe. When it is not safe, dynamic programming often becomes the right tool.
Decision Rule
Use greedy only when you can justify that each local choice can be extended to a global optimum. Use dynamic programming when choices interact over time and subproblems overlap.
Comparison Table
| Feature | Greedy | Dynamic programming |
|---|---|---|
| Choice style | commit to best local move | compare subproblem states |
| Proof need | exchange argument, stays-ahead proof, matroid-like structure | recurrence and induction |
| Memory | often small | table or memo cache |
| Typical examples | interval scheduling, Huffman coding, Dijkstra with nonnegative weights | knapsack, edit distance, LCS |
| Failure signal | early local choice blocks future optimum | repeated subproblems appear |
Worked Example
Coin change with coin system {1, 3, 4} and target 6 breaks the naive greedy rule. Greedy picks 4, then 1, then 1, using three coins. Dynamic programming finds 3 + 3, using two coins.
The local best coin was not globally best.
Common Mistakes
| Mistake | Correction |
|---|---|
| Calling every optimization problem DP. | If a local choice is provably safe, greedy may be simpler. |
| Trusting greedy because it works on sample tests. | Greedy needs proof, not anecdotes. |
| Writing DP without defining state. | State design is the main work of DP. |
Diagnostic Questions
| Question | Answer signal |
|---|---|
| What proof does greedy usually need? | A reason the local choice can be part of an optimal solution. |
| What two signals suggest DP? | Optimal substructure and overlapping subproblems. |
| Why does coin change sometimes break greedy? | The largest coin can block a better combination. |
Exercises
- Beginner: Decide whether activity selection is greedy or DP.
- Beginner: Decide whether edit distance is greedy or DP.
- Beginner: Explain optimal substructure in plain language.
- Intermediate: Give a counterexample to a greedy coin-change algorithm.
- Intermediate: Derive the recurrence for 0/1 knapsack.
- Challenge: Prove a greedy interval scheduling algorithm by an exchange argument.
References
- MIT OpenCourseWare. 6.006 Introduction to Algorithms, Spring 2020: https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-spring-2020/
- MIT OpenCourseWare. 6.046J Design and Analysis of Algorithms, Spring 2015: https://ocw.mit.edu/courses/6-046j-design-and-analysis-of-algorithms-spring-2015/