AntInLoop

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, then 1, then 1 → 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>

---

Related Algorithms