coin change problem
The problem of making a given amount of money with the fewest coins from a set of coin values.
In more detail
Greedily taking the largest coin that fits is optimal for coin systems such as 1, 5, 10 and 25, but fails for others: with coins 1, 3 and 4, greedy makes 6 as 4 + 1 + 1 while 3 + 3 uses fewer. Dynamic programming always finds the minimum. It is the course's standard warning that greedy needs proof.
Related terms
- greedy algorithm — An algorithm that builds a solution step by step, always taking the choice that looks best right now and never revisiting it.
- dynamic programming — A technique that solves a problem by breaking it into overlapping subproblems, solving each only once and storing the answers for reuse.
- counterexample — A single specific input that shows a claim or algorithm is wrong.
Taught in
- Greedy Algorithms: When Local Is Global — Algorithms & Data Structures for Working Engineers
- Recognising The Pattern — Algorithms & Data Structures for Working Engineers