Recursion & DP Target: 15s
Greedy never backtracks. DP explores all options. If you can't prove greedy works with an exchange argument, use DP.
GREEDY vs DP — KEY DIFFERENCE
─────────────────────────────
GREEDY: make locally optimal choice at each step
→ Never reconsider previous choices
→ No overlapping subproblems needed
→ O(n) or O(n log n) typically
DP: consider ALL choices, pick globally optimal
→ May revisit states through memoization
→ Requires overlapping subproblems
→ O(n²) or O(n*W) typically
HOW TO TELL:
□ Can you prove greedy works? (exchange argument)
□ Does local best = global best? → greedy
□ Counterexample found? → need DP
CLASSIC GREEDY:
Activity selection, interval scheduling, Huffman,
jump game, gas station, assign cookies
CLASSIC DP:
Knapsack, coin change, LCS, edit distance
TRAP: coin change is DP (greedy fails for [1,3,4] target=6)
but interval scheduling is greedy (sort by end time)Type it from memory. Go.