the coin-change problem
You are given a set of coin denominations (say 1, 3, and 4) and a target amount, and you have an unlimited supply of each coin. The question comes in two common flavors: what is the fewest coins that add up exactly to the amount, and (a counting version) in how many distinct ways can you make the amount. Both are everyday-feeling problems — a cashier making change — but the surprising part is that the obvious greedy strategy of always grabbing the largest coin that fits can give the wrong answer for the minimization version with arbitrary denominations.
For the minimum-coins version, let dp[x] be the fewest coins summing to amount x. The transition tries each coin as the last coin used: dp[x] = 1 + min over coins c with c <= x of dp[x - c]. The base case is dp[0] = 0 (zero coins make zero), and every other dp[x] starts at infinity so that amounts you cannot form stay infinite. Filling dp[0], dp[1], ..., dp[amount] in increasing order takes O(amount times number_of_coins) time. For the counting version, let ways[x] be the number of ways to make x; you process the coins one at a time and, for each coin c, update ways[x] += ways[x - c] for x from c upward — looping coins on the outside and amounts on the inside is what counts each combination once rather than counting orderings.
Coin change is the canonical place to see that greedy is not a proof. With US coins (1, 5, 10, 25) greedy happens to be optimal, which lulls people into trusting it; but with denominations like 1, 3, 4 and target 6, greedy takes 4 then 1 then 1 (three coins), while the optimal is 3 + 3 (two coins) — the DP finds the 2-coin answer that greedy misses. Two more honest points: like 0/1 knapsack, the O(amount times coins) running time is pseudo-polynomial (the amount is exponential in its bit-length), and the minimum-coins and count-the-ways versions are genuinely different DPs whose loop structures must not be swapped, since getting the loop nesting wrong in the counting version silently counts the same combination in multiple orders.
Coins 1, 3, 4, target 6. Greedy grabs 4, then 1, then 1 — three coins. The DP computes dp[6] = 1 + min(dp[5], dp[3], dp[2]) and, tracing the chain, finds dp[6] = 2 via 3 + 3. Greedy's locally-largest choice missed the better pair.
Greedy's largest-coin-first can be wrong; the DP tries every last coin and is optimal.
Greedy works for some coin systems (like US coins) but not all — so do not assume it. And the minimum-coins DP and the count-the-ways DP differ: in the counting version, loop coins outside and amounts inside, or you will overcount the same combination in different orders.