Greedy vs Dynamic Programming: What is the Difference?
Compare greedy algorithms and dynamic programming — when each works, why greedy can fail, and interview-ready examples.
Expected Interview Answer
Greedy algorithms make the locally optimal choice at each step and never reconsider it, while dynamic programming explores overlapping subproblems and combines their optimal solutions, only working when the problem has optimal substructure and, for DP, overlapping subproblems.
Greedy works when a problem exhibits the "greedy-choice property" — a locally best decision always leads to a globally best solution, as in Kruskal’s minimum spanning tree or coin change with canonical coin systems. Dynamic programming is needed when local choices can be wrong in hindsight, so the algorithm must compute and cache solutions to smaller subproblems (memoization or tabulation) and build up the answer, as in the knapsack problem or edit distance. Greedy is typically faster, O(n log n) or better, but not always correct; DP is more broadly correct but usually costs more time and space, often O(n²) or O(n·W).
- Greedy: simpler code, faster runtime when applicable
- DP: correct even when local choices can be misleading
- DP avoids recomputation via memoization/tabulation
- Choosing correctly avoids subtly wrong greedy solutions
AI Mentor Explanation
A greedy team-selector picks whichever available player has the single highest batting average right now for each remaining slot, never revisiting earlier picks even if a better overall combination existed. A dynamic-programming selector instead considers every combination of remaining budget and player pool, remembers the best sub-squad achievable at each budget level, and builds the optimal full squad from those cached sub-answers. The greedy approach is fast but can lock in a suboptimal squad; the DP approach is slower but guarantees the best possible team within budget.
Step-by-Step Explanation
Step 1
Check optimal substructure
Confirm the problem’s optimal solution can be built from optimal solutions to its subproblems.
Step 2
Test the greedy-choice property
Verify a locally best choice never needs revisiting; if a counterexample exists, greedy is wrong.
Step 3
Look for overlapping subproblems
If the same subproblem recurs across branches, memoize it — that is the DP signal.
Step 4
Pick the cheaper correct approach
Use greedy when its property holds for speed; otherwise use DP for guaranteed correctness.
What Interviewer Expects
- Clear definition of both paradigms with a concrete example each
- Recognition that greedy is not always correct, with a counterexample (e.g. non-canonical coin systems)
- Explanation of memoization vs. tabulation in DP
- Complexity comparison between the two approaches on the same problem
Common Mistakes
- Assuming greedy always works because it is simpler
- Applying greedy coin-change to non-canonical denominations and getting a wrong answer
- Writing DP without recognizing overlapping subproblems, leading to redundant recomputation
- Confusing memoization (top-down) with tabulation (bottom-up) as if they were different algorithms rather than implementation styles
Best Answer (HR Friendly)
“Greedy algorithms make the best choice available right now and never look back, which is fast but only works for certain problems. Dynamic programming instead breaks a problem into smaller overlapping pieces, solves and remembers each piece once, and combines them — it is more broadly correct but takes more computation.”
Code Example
def greedy_coin_change(coins, amount):
coins = sorted(coins, reverse=True)
count = 0
for c in coins:
while amount >= c:
amount -= c
count += 1
return count if amount == 0 else -1
def dp_coin_change(coins, amount):
dp = [0] + [float('inf')] * amount
for a in range(1, amount + 1):
for c in coins:
if c <= a:
dp[a] = min(dp[a], dp[a - c] + 1)
return dp[amount] if dp[amount] != float('inf') else -1Follow-up Questions
- Give an example where greedy fails but DP succeeds on the same problem.
- What is the difference between memoization and tabulation?
- How do you identify optimal substructure in a new problem?
- When would you prefer greedy despite DP being more broadly correct?
MCQ Practice
1. Which property must hold for a greedy algorithm to guarantee a correct global solution?
The greedy-choice property guarantees a locally optimal choice always leads to a globally optimal solution.
2. What signals that a problem needs dynamic programming rather than plain recursion?
Overlapping subproblems mean the same subproblem is solved repeatedly, which DP avoids via caching.
3. Greedy coin-change fails to find the optimal answer when:
With denominations like 1, 3, 4, greedy picks 4+1+1 (3 coins) instead of the optimal 3+3 (2 coins).
Flash Cards
What is the greedy-choice property? — A locally optimal choice at each step always leads to a globally optimal solution.
What two conditions justify using DP? — Optimal substructure and overlapping subproblems.
Name a classic greedy-correct problem. — Kruskal’s or Prim’s minimum spanning tree algorithm.
Name a classic problem where greedy fails but DP succeeds. — 0/1 Knapsack — greedy by value/weight ratio can be suboptimal; DP guarantees the optimum.