53. How do you choose between dynamic programming and greedy?
MediumDynamic programming
Technical
Show model answer
Try to find a counterexample to the greedy choice. If a locally best choice can block a better overall answer (coin change with coins [1, 3, 4] and amount 6: greedy uses 4 + 1 + 1 but 3 + 3 is better), you need DP to consider all options. If an exchange argument proves the greedy choice is always safe, greedy is simpler and faster.