Greedy Algorithm vs Dynamic Programming
People think a greedy algorithm always finds the best answer, and it does not. Greedy takes the best-looking step now and never goes back. Dynamic programming works out the best answer for each smaller case first, then builds on them. Greedy is faster when it works. With coins of 4, 3 and 1, greedy makes 6 with three coins, and dynamic programming finds two.
Greedy Algorithm
Taking the choice that looks best at each step. It never goes back.
A greedy algorithm builds an answer one step at a time. At each step it takes the choice that looks best right now. It never goes back to change an earlier choice. That makes it fast and simple. For some problems it gives the best answer, and for others it misses. Giving change with coins of 1, 5, 10 and 25 works greedily; coins of 1, 3 and 4 do not.
Dynamic Programming
Saving the answers to small parts that repeat. Each is solved once.
Dynamic programming breaks a big problem into small ones that repeat. It saves each small answer. When the same small problem comes up again, it reuses the saved answer. You can save answers as you go from the top; that is called memoization. Or you can fill a table from the smallest case up. It turns many jobs that would take years into ones that take a second.
In one line
- Greedy Algorithm
- Taking the choice that looks best at each step. It never goes back.
- Dynamic Programming
- Saving the answers to small parts that repeat. Each is solved once.