Greedy vs Dynamic Programming
Quick Answer
Use Greedy when making the locally optimal choice at each step provably leads to the global optimum (the problem has the greedy choice property). Use Dynamic Programming when a greedy approach fails because the problem has overlapping subproblems and you need to consider all possibilities to find the optimum.
Side-by-Side Comparison
| Aspect | Greedy | Dynamic Programming |
|---|---|---|
| Approach | Make the best local choice at each step | Solve all subproblems, combine for global optimum |
| Guarantee | Optimal only if greedy choice property holds | Always optimal (if formulated correctly) |
| Time complexity | Usually O(n log n) with sorting, or O(n) | O(n * W) or O(n^2) depending on problem |
| Space complexity | O(1) to O(n) | O(n) to O(n * W) for DP table |
| Backtracking needed? | No (never revisits decisions) | No (but considers all options via subproblems) |
| Required properties | Greedy choice property + optimal substructure | Overlapping subproblems + optimal substructure |
| Implementation | Sort + iterate (usually simpler code) | Memoization or tabulation (more complex code) |
When to Use Greedy
- -The problem has the greedy choice property: a locally optimal choice is part of a globally optimal solution.
- -Activity selection / interval scheduling: pick the event that ends earliest.
- -Huffman coding: always merge the two lowest-frequency nodes.
- -Minimum spanning tree (Kruskal's / Prim's): always take the cheapest safe edge.
- -Problems where sorting by one criterion and iterating gives the answer (jump game, gas station).
When to Use Dynamic Programming
- -The problem has overlapping subproblems — you compute the same subproblem multiple times without memoization.
- -Making a locally optimal choice does NOT guarantee a global optimum. You need to evaluate all options.
- -Counting problems — how many ways to reach a target, how many distinct paths.
- -Optimization over sequences — longest increasing subsequence, edit distance, knapsack.
- -The problem can be broken into stages where each stage depends on previous stages' results.
Key Differences
Decision permanence
Greedy commits irrevocably to each choice and never looks back. DP explores all possibilities by solving every subproblem and combining results. This is why greedy is faster but only works when the greedy choice property holds.
How to recognize each
Greedy: Can you prove that always picking the "best" option at each step leads to the overall best solution? If yes, greedy works. DP: Can you find a counterexample where greedy fails? If yes, you need DP. Also, if the problem asks "count the number of ways", greedy almost never applies.
Complexity trade-off
Greedy algorithms are typically O(n log n) or O(n) and use minimal extra space. DP algorithms often require O(n^2) or O(n * W) time and space for the DP table. When greedy works, it is the superior approach.
How to Decide
- Try greedy first. It is simpler and faster. Formulate a greedy strategy (e.g., always pick the largest/smallest/earliest).
- Look for a counterexample. Can you construct an input where the greedy strategy gives a wrong answer? If yes, you need DP.
- Does the problem ask "count the number of ways"? Almost always DP (greedy gives one solution, not a count).
- Does the problem involve making a sequence of dependent decisions? If choosing option A now affects what options are available later, consider DP.
- Is there a known greedy proof? Classic greedy problems (activity selection, fractional knapsack, Huffman) have well-known proofs.
- Does the problem resemble a known DP pattern? Knapsack, LCS, edit distance, coin change with min coins — these all require DP.
Example Problems
Greedy
- 1.Jump Game — Track the farthest reachable index; greedily extend the reach at each step.
- 2.Activity Selection — Sort by end time, greedily pick the next non-overlapping activity.
- 3.Assign Cookies — Sort children by greed and cookies by size, assign the smallest sufficient cookie.
Dynamic Programming
- 1.Coin Change — Find min coins to make amount. Greedy (largest coin first) fails for non-standard denominations.
- 2.Longest Increasing Subsequence — Greedy picks the smallest next element but misses longer subsequences found by skipping.
- 3.Edit Distance — No greedy rule exists; you must explore insert, delete, and replace at each position.
Problems That Look Greedy But Need DP
- 1.Coin Change (non-standard denominations) — With coins [1, 3, 4] and target 6, greedy picks 4+1+1=3 coins, but optimal is 3+3=2 coins. You must try all combinations via DP.
- 2.0/1 Knapsack — Unlike fractional knapsack (greedy works), 0/1 knapsack requires DP because you cannot take partial items. Greedily picking the best value/weight ratio can miss the optimal selection.