Skip to interview prep
Apexed

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.

How do you choose between dynamic programming and greedy — Data structures & algorithms interview question — Apexed