Problem Statement
Explain both the Coin Change problems: minimum coins needed and number of ways to make change. Why does greedy work for some coin systems but not others?
Explanation
There are two classic Coin Change problems. The first asks for the minimum number of coins needed to make a given amount. The second asks for the number of different ways to make the amount. Both require different approaches and have different properties.
The Minimum Coins problem gives you coin denominations and a target amount, and asks for the minimum number of coins needed to make that amount. This is an optimization problem requiring dynamic programming in the general case. The DP state is dp of i equals minimum coins needed to make amount i. The recurrence relation is: dp of i equals 1 plus min of dp of i minus coin for all coins where coin is less than or equal to i. Base case is dp of 0 equals 0 as zero coins make amount 0. Time complexity is O of n times amount where n is number of coin types. Space complexity is O of amount.
The greedy approach for minimum coins always picks the largest coin possible. For certain coin systems like US coins with denominations 1, 5, 10, 25, this greedy approach gives optimal solutions. For example, making 30 cents greedily gives 25 plus 5 equals 2 coins, which is optimal. However, for arbitrary coin systems, greedy may fail.
Consider coins 1, 3, 4 and amount 6. The greedy approach picks 4 plus 1 plus 1 equals 3 coins. But the optimal solution is 3 plus 3 equals 2 coins. This shows greedy does not work for all coin systems. The reason is that taking the largest coin first may prevent using combinations of smaller coins that sum to the optimal solution.
Canonical coin systems are those where greedy always gives optimal solutions. US coins are canonical. For a coin system to be canonical, it must satisfy certain mathematical properties related to how denominations relate to each other. Proving canonicity requires checking all possible amounts up to a certain threshold.
The Counting Ways problem asks for the number of different combinations of coins that sum to the target amount. Order does not matter, so 1 plus 2 and 2 plus 1 count as the same way. This is a counting problem also requiring DP. The DP state is dp of i equals number of ways to make amount i. The recurrence relation is: dp of i plus equals dp of i minus coin for all coins where coin is less than or equal to i. Base case is dp of 0 equals 1 as one way to make zero using no coins.
A crucial difference is the iteration order. To avoid counting duplicate combinations, we iterate over coins in the outer loop and amounts in the inner loop. This ensures each combination is counted once. If we iterate amounts in outer loop, we count permutations instead of combinations.
The unbounded version allows using each coin unlimited times. The bounded version limits how many times each coin can be used, requiring tracking both amount and coin counts.
Applications include making change in vending machines and stores, currency conversion and exchange, resource allocation problems where resources have different values, and optimizing payments in financial systems. Dynamic programming is essential for arbitrary coin systems to guarantee optimal or correct solutions.