Greedy Algorithms vs Dynamic Programming

A greedy algorithm builds a solution by making the locally best choice at each step and never looking back. Dynamic programming builds a solution by systematically considering every relevant subproblem and combining their optimal answers. Both are strategies for optimization problems, and both can produce genuinely optimal results — the difference is that greedy only works when a problem has a specific structural guarantee, and dynamic programming works more broadly but costs more to run.

How a greedy algorithm thinks

At each decision point, a greedy algorithm picks whatever option looks best right now, commits to it permanently, and moves to the next decision without reconsidering earlier choices. It never backtracks and never explores alternatives once a choice is made.

Making change with the fewest coins is the classic illustration. Given denominations of 25, 10, 5, and 1 cent, a greedy approach for 41 cents picks the largest coin that fits at each step: one 25, one 10, one 5, one 1 — four coins, which happens to be optimal for this denomination set. The greedy choice works here because U.S. coin denominations have a property that makes the locally best pick always compatible with a globally optimal solution.

Where greedy quietly breaks

Change that “just works” for U.S. coins can fail entirely for other denomination sets. Given coins of 1, 3, and 4, greedily making 6 cents picks a 4, then two 1s — three coins — when two 3s would only need two coins. Greedy commits to the 4 immediately because it’s the largest denomination that fits, without any way to reconsider once a better combination becomes visible in hindsight. This is the general risk with greedy algorithms: a locally optimal choice can foreclose a better global solution, and there’s no way to detect that without checking against other approaches or proving the greedy property holds for the specific problem.

Greedy algorithms are only guaranteed correct when a problem exhibits the greedy-choice property (a locally optimal choice is always part of some globally optimal solution) and optimal substructure (an optimal solution to the problem contains optimal solutions to its subproblems). Proving these hold is the actual work in justifying a greedy approach — without that proof, a greedy algorithm is just a fast heuristic that might happen to be wrong.

How dynamic programming thinks

Dynamic programming, covered in more depth in dynamic programming, explained, doesn’t commit to a single choice per step. Instead, it solves every relevant subproblem once, stores each result, and builds the final answer by combining those stored subproblem solutions — which lets it correctly handle cases where the locally attractive choice isn’t actually part of the best overall solution.

Applied to the 1-3-4 coin problem, a DP approach computes the minimum coins needed for every amount from 0 up to the target, using previously computed smaller amounts to build each larger one:

minCoins[0] = 0
minCoins[amount] = 1 + min(minCoins[amount - c] for each coin c <= amount)

For 6 cents, this correctly finds minCoins[3] + minCoins[3] = 1 + 1 = 2 coins, because it actually compares every combination rather than committing to the largest denomination first. The cost of that correctness is that DP has to compute and store an answer for every subproblem, not just walk straight to the end.

Side by side

	Greedy	Dynamic programming
Strategy	Locally best choice, no backtracking	Solve and cache every relevant subproblem
Correctness guarantee	Only when the greedy-choice property provably holds	Whenever optimal substructure holds
Time complexity	Usually faster — often a single pass	Usually slower — proportional to subproblem count
Space usage	Minimal — no need to store subproblem results	Requires memoization or a table of subproblem results
Failure mode	Can silently produce a wrong answer	Correct but more expensive to compute
Classic examples	Minimum spanning tree, Huffman coding, interval scheduling	Fibonacci with memoization, edit distance, knapsack

When to reach for which

Use greedy when you can prove — or already know from established results — that the greedy-choice property holds for the specific problem: constructing a minimum spanning tree, building a Huffman coding tree, or scheduling non-overlapping intervals to maximize count are classic cases where greedy is both correct and considerably faster than a full DP formulation would be.

Use dynamic programming when subproblems overlap and the locally attractive choice isn’t reliably part of the global optimum — the 1-3-4 coin problem, the 0/1 knapsack problem, edit distance between two strings, or any optimization problem where an early “obviously good” choice can be shown to sometimes produce a worse final answer. If you’re unsure whether greedy applies, it usually doesn’t; the safer default is DP, with a greedy approach only substituted in once its correctness is actually established for that problem.

Complexity is the real trade-off

Reaching for DP by default isn’t free. A greedy algorithm often runs in time proportional to the number of decisions — frequently linear or log-linear, depending on how choices are ranked, as covered in Big O notation, explained. Dynamic programming’s cost scales with the number of distinct subproblems, which can be quadratic or worse depending on the problem’s structure. That gap is exactly why greedy is worth using whenever it’s provably correct — the speed difference compounds at scale, in the same way that quicksort vs mergesort or BFS vs DFS trade-offs come down to matching an algorithm’s guarantees to what a specific problem actually needs.

The takeaway

Greedy algorithms are fast because they never look back, but that speed only produces a correct answer when the problem has a provable greedy-choice property — otherwise an early “obviously good” pick can lock out the actual optimal solution. Dynamic programming is slower but correct more broadly, because it considers every relevant subproblem rather than committing early. When in doubt about whether a problem’s greedy choice is safe, default to dynamic programming, and only switch to greedy once its correctness for that specific problem is established.