Greedy and dynamic programming both require optimal substructure. The deciding question is whether a single local choice is provably safe, or whether you must explore multiple choices and combine their results.
The decision table
| Operation | Best | Average | Worst | Note |
|---|---|---|---|---|
| Local choice is provably optimal | Greedy | one pass, O(1) state | wrong if greedy-choice property fails | |
| Choice depends on future subproblems | DP | memoize / tabulate | higher time & space | |
| Need to count all ways or all solutions | DP (or backtracking) | greedy can't count | — |
How to tell them apart
- Greedy — you can argue (exchange argument) that committing to the best-looking option now never blocks a better future. One sort + one sweep, O(1) or O(log n) extra state.
- DP — the value of a choice depends on subproblem results you can't evaluate yet, so you try all choices and keep the best. Overlapping subproblems make memoization pay off.
The classic contrast: knapsack
- Fractional knapsack is greedy: take items by descending value/weight, splitting the last one. The greedy choice is safe because you can always fill the remaining capacity optimally.
- 0/1 knapsack is DP: you can't split items, so taking the best ratio item can lock out a better whole-item combination. You must consider take-vs-skip for every item —
dp[i][w].
The coin-change tell
- US/euro denominations → greedy (largest coin first) happens to be optimal, but only because of the specific denomination structure.
- Arbitrary denominations like
{1, 3, 4}, target6→ greedy gives4+1+1(3 coins), DP gives3+3(2 coins). Coin Change is a DP problem — never assume greedy.
Practical heuristic for the interview
- Try greedy first — it's simpler and faster.
- Immediately stress-test it with a small adversarial input.
- If you find a counterexample, switch to DP. If you can sketch an exchange-argument proof, commit to greedy.