Dynamic Programming vs. Greedy Algorithms
A practical guide to distinguishing when a fast Greedy choice is provably optimal versus when overlapping subproblems require Dynamic Programming, illustrated with concrete counterexamples.
Difficulty: Medium · Interactive Visualizer · C++ / Python / Java / JS Code
Dynamic Programming vs. Greedy Algorithms
Both Greedy and Dynamic Programming (DP) solve optimization problems with optimal substructure, yet choosing the wrong one either produces a wrong answer (Greedy when DP was needed) or TLE (DP when Greedy worked in $O(n \log n)$).
At a Glance
| Criterion | Greedy | Dynamic Programming |
| :--- | :--- | :--- |
| Decision Style | Commits to the locally best choice once, never reconsiders | Evaluates all valid transitions and caches subproblems |
| Requires Greedy-Choice Property? | Yes (provable via exchange argument) | No |
| Classic Examples | Activity Selection, Fractional Knapsack, Huffman, Kruskal, Dijkstra | 0/1 Knapsack, Coin Change, Edit Distance, LCS |
---
Concrete Counterexample: Coin Change (coins = {1, 3, 4}, amount = 6)
- Greedy picks
4, then1, then1→ 3 coins (WRONG!). - DP evaluates all choices and finds
3 + 3→ 2 coins (OPTIMAL!).
<details>
<summary>Show C++ Comparison</summary>
#include <algorithm>
#include <iostream>
#include <vector>
int greedyCoins(std::vector<int> coins, int amount) {
std::sort(coins.rbegin(), coins.rend());
int cnt = 0;
for (int c : coins) { cnt += amount / c; amount %= c; }
return amount == 0 ? cnt : -1;
}
int dpCoins(const std::vector<int>& coins, int amount) {
std::vector<int> dp(amount + 1, amount + 1);
dp[0] = 0;
for (int a = 1; a <= amount; ++a)
for (int c : coins)
if (a >= c) dp[a] = std::min(dp[a], dp[a - c] + 1);
return dp[amount] > amount ? -1 : dp[amount];
}
int main() {
std::vector<int> coins = {1, 3, 4};
std::cout << "Greedy=" << greedyCoins(coins, 6) << " DP=" << dpCoins(coins, 6) << "\n"; // Greedy=3 DP=2
return 0;
}
</details>
---