Skip to content
BENIBIX Learn

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.

Development🧮 Algorithms & Data Structures

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.

Example
Emma makes 6 cents from coins of 1, 3 and 4. Greedy takes 4, 1, 1, three coins, but 3 and 3 needs only two.
Why it matters
When it works it is the fastest way, and Dijkstra's algorithm is one. You must check that it works first.
Full entry
Development🧮 Algorithms & Data Structures

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.

Example
Jack works out the 50th Fibonacci number. Saving each smaller one makes 49 additions, not billions of calls.
Why it matters
Route maps, spell checkers and DNA tests all use it. Without it, those jobs would never finish.
Full entry

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.