greedy algorithm
A greedy algorithm builds up a solution one step at a time, and at each step grabs whatever looks best right now — the locally optimal choice — without ever reconsidering. Think of making change for a customer with a fistful of coins: you hand over the largest coin that still fits, then the largest that fits the remainder, and so on. It is the simplest, most natural strategy there is, and when it works it is wonderfully fast, often just a single pass after sorting.
The catch — and it is a big one — is that the best choice now is not always part of the best choice overall. Greedy is only correct when the problem has a special property: that making the locally best choice never closes off the path to a globally best answer (often called the greedy-choice property, alongside optimal substructure). With the everyday US/euro coin systems, take-the-biggest-coin always yields the fewest coins. But invent a coin system of {1, 3, 4} and ask for 6: greedy takes 4, then 1, then 1 — three coins — when the true best is 3 + 3, just two. Same algorithm, different data, wrong answer.
So the discipline of greedy design is proof, not just plausibility: you must argue that the greedy choice is safe, or find a counterexample that kills it. Where it does hold, greedy is the method of choice — Huffman coding builds an optimal prefix code by repeatedly merging the two least-frequent symbols; Dijkstra's shortest-path and the standard minimum-spanning-tree algorithms (Kruskal, Prim) are greedy at heart. When greedy fails, the usual rescue is dynamic programming, which considers more options rather than committing to the first that looks good.
// Greedy change: always take the largest coin that fits.
int greedyCount(vector<int> coins, int amount) {
sort(coins.rbegin(), coins.rend());
int n = 0;
for (int c : coins)
while (amount >= c) { amount -= c; ++n; }
return n; // correct ONLY if the coin system is canonical
}With coins {1,3,4} and amount 6, greedy gives 4+1+1 (3 coins); optimal is 3+3 (2 coins).
Greedy and dynamic programming are easy to confuse: both need optimal substructure, but greedy commits to one choice at each step and never looks back, while DP keeps several candidate answers and lets the table decide. If you cannot prove the greedy choice is safe, reach for DP.