Grab It Now, or Plan the Whole Thing?

The four lines that decide it

Coin change is the cleanest place to see the split, because the same problem statement flips between the two techniques depending on nothing but the coin set. You are given denominations and a target, and you want the fewest coins that sum to it exactly. The obvious rule — the one every cashier uses — is to take the biggest coin that still fits, subtract, and repeat. That is a greedy algorithm, and with denominations {1, 3, 4} and a target of 6 it goes:

Three coins, and greedy is finished — it never revisits the decision to grab the 4, because not revisiting is the whole definition. Dynamic programming refuses to grab anything. It works out the cheapest way to make 1, then 2, then 3, all the way up to the target, storing each answer as it goes. When it reaches 6 it tries every coin as the last coin and takes the best of the stored answers underneath:

Two coins. Same problem, same denominations, and greedy is not merely unlucky — it is provably wrong here, and it is wrong for a reason you can point at. Taking the 4 leaves a remainder of 2, and 2 is the single worst amount this coin set can produce: it costs two coins where 3 and 4 each cost one. Greedy paid one coin to walk into the most expensive corner of the problem, and had already thrown away its right to reconsider.

What both need, and what only greedy needs

Greedy and DP are not opposites. They share a prerequisite and differ by exactly one extra condition, and naming the two precisely is what turns "try greedy and see" into an actual decision.

The greedy-choice property is the part you have to prove, and the standard proof is an exchange argument. Take any optimal solution. If it does not already contain your greedy choice, modify it so it does — swap your choice in, swap something else out — and show the modified solution is still valid and no worse. If that swap always works, there is always an optimum containing the greedy choice, so committing costs nothing. Peel that choice off and the same argument applies to the smaller problem left behind, which is the induction that carries you to a full proof.

There is one shortcut worth knowing. Some problems are matroids — set systems where every subset of an independent set is independent, and where any smaller independent set can always absorb an element from a larger one. For a matroid with weighted elements, "sort by weight and take anything that keeps the set independent" is provably optimal, no bespoke proof required. That single theorem is why Kruskal's algorithm works: forests in a graph form a matroid, so greedily taking the cheapest edge that does not close a cycle yields a minimum spanning tree. Prim's arrives at the same optimum from a different greedy angle. If you can recognize your problem as a matroid, you are done arguing — greedy is safe.

The decision table

In practice you will not derive matroid theory at a whiteboard. You will pattern-match on the shape of the problem. These are the signals worth memorizing, each with a page on this site where the pattern is played out in full.

Two entries in that table deserve a second look, because they are the same problem twice. Fractional knapsack — where you may take half an item — is greedy: sort by value per unit weight, fill from the top, and the last item is cut to fit. 0/1 knapsack, where items are indivisible, is DP. Nothing changed except whether you are allowed to cut, and the entire technique flipped. Likewise, unweighted interval scheduling is greedy, but attach a value to each interval and the weighted version needs DP. When you see a problem you "know" is greedy, check whether this variant is really the variant you proved.

What each one costs

The reason to care is not elegance, it is money. A greedy algorithm is usually a sort followed by one linear pass: O(n log n) time and O(1) extra space, with a loop body of a few instructions. Dynamic programming has to materialize an answer per subproblem, so its cost is the size of the state space times the work per state. Coin change is O(n·W) time and O(W) space for n denominations and target W; 0/1 knapsack is O(n·W) for capacity W.

That W matters more than it looks. It is a value in the input, not a count of items, so a target of one billion means a billion table cells even though the input is a handful of numbers. This is what "pseudo-polynomial" means: polynomial in the numeric value, exponential in the number of bits used to write it down. A greedy solution to the same problem would not care how large the target is.

So the honest order of operations is: try greedy first. Not because it is more likely to be right, but because the payoff when it is right is enormous and the cost of checking is tiny — one adversarial example, worked by hand, in under a minute. Reach for DP when you have an actual counterexample in hand, not as a reflex. The two implementations, side by side, make the trade concrete:

Both fit on a screen. The DP is barely longer — its cost is the table, not the code. And notice what the inner loop of the DP is doing: it is trying every coin as the last coin, which is precisely the reconsideration greedy refuses to perform. That single extra loop is the difference between 3 coins and 2.

One last practical note: the two are not mutually exclusive. Many real solutions use greedy inside DP — to order states, to prune branches, to produce a bound that lets branch-and-bound discard subtrees. And a memoized recursion (top-down DP) is often the fastest way to get a correct answer you can then optimize into a bottom-up table. Correct first, cheap second.

Check yourself