Coin Change and Counting Ways
28 min · Intermediate
Need help? Ask a tutor on WhatsApp (opens in a new tab)Here the state is an amount, and the choices are the coins. The same table can ask for the fewest coins or count the ways, and the loop order decides what is counted.
Fewest coins for an amount
Unbounded knapsack is choosing items that can be used any number of times to reach a target, such as coins for an amount. The state is the amount left to fill.
A till has coins of some values, as many of each as needed. To pay an amount, try each coin as the last one: the best for amount a is one coin plus the best for a - coin.
def fewest(coins, amount): INF = float("inf") dp = [0] + [INF] * amount for a in range(1, amount + 1): for c in coins: if c <= a: dp[a] = min(dp[a], dp[a - c] + 1) return dp[amount] if dp[amount] != INF else -1
print(fewest([1, 3, 4], 6))Example 1 · An amount that cannot be paid
def fewest(coins, amount): INF = float("inf") dp = [0] + [INF] * amount for a in range(1, amount + 1): for c in coins: if c <= a: dp[a] = min(dp[a], dp[a - c] + 1) return dp[amount] if dp[amount] != INF else -1
print(fewest([5, 10], 7))print(fewest([5, 10], 25))print(fewest([2], 0))-1 3 0
What this code does
- Amount 7 cannot be built from 5 and 10, so the cell stays infinity and the function returns -1.
- Amount 0 needs no coins, which is the base case.
dp[a] is the fewest coins for amount a, and infinity means it cannot be paid. Time is O(amount x coins) and space is O(amount). float("inf") plus 1 is still infinity, so impossible amounts stay impossible.
Why greedy fails
Taking the largest coin first looks natural. For coins 1, 3 and 4 and an amount of 6, greedy takes 4, 1, 1, which is three coins. The table finds 3 + 3, which is two.
coins = [1, 3, 4]amount = 6greedy = 0left = amountfor c in sorted(coins, reverse=True): greedy += left // c left %= cprint("greedy:", greedy)Example 2 · Greedy against DP
def greedy(coins, amount): count = 0 for c in sorted(coins, reverse=True): count += amount // c amount %= c return count if amount == 0 else -1
def fewest(coins, amount): INF = float("inf") dp = [0] + [INF] * amount for a in range(1, amount + 1): for c in coins: if c <= a: dp[a] = min(dp[a], dp[a - c] + 1) return dp[amount] if dp[amount] != INF else -1
for coins in ([1, 5, 10, 25], [1, 3, 4]): print(coins, greedy(coins, 6), fewest(coins, 6))[1, 5, 10, 25] 2 2 [1, 3, 4] 3 2
What this code does
- For the common coins 1, 5, 10 and 25 greedy and DP agree. For 1, 3 and 4 they differ.
- Greedy can also miss a possible payment: coins [5, 3] with amount 9 give -1 from greedy.
Example 3 · Which coins were used
coins = [1, 3, 4]amount = 10INF = float("inf")dp = [0] + [INF] * amountlast = [0] * (amount + 1)for a in range(1, amount + 1): for c in coins: if c <= a and dp[a - c] + 1 < dp[a]: dp[a] = dp[a - c] + 1 last[a] = cused, a = [], amountwhile a > 0: used.append(last[a]) a -= last[a]print(dp[amount], used)3 [3, 3, 4]
What this code does
last[a]remembers the coin that gave the best answer for a. Walking back from the amount lists the coins.- Several answers can tie. This one keeps the first coin that reaches the best count.
Greedy is right for some coin systems but not all. DP checks every last coin, so it is right for any list of coins. Say this in an interview when you are asked why you did not use greedy.
Counting the ways to pay
A combination count treats a payment as a set of coins, so the order does not matter. It is built with the coins in the outer loop and the amounts in the inner loop.
Now count the different ways to pay an amount, where 1 + 2 and 2 + 1 are the same way. Loop over the coins first, and inside it loop over the amounts. Each coin is then added once in a fixed order.
def count_ways(coins, amount): dp = [1] + [0] * amount for c in coins: for a in range(c, amount + 1): dp[a] += dp[a - c] return dp[amount]
print(count_ways([1, 2, 5], 11))Example 4 · Sets of coins
def count_ways(coins, amount): dp = [1] + [0] * amount for c in coins: for a in range(c, amount + 1): dp[a] += dp[a - c] return dp[amount]
print(count_ways([2], 3))print(count_ways([1, 2, 3], 4))print(count_ways([1, 2, 5], 100))0 4 541
What this code does
- With only coin 2, amount 3 has no way, so the answer is 0.
- The last number is large but exact, because Python has no overflow.
dp[a] counts the ways using the coins processed so far. After coin c is processed, every way may use c any number of times. Time is O(amount x coins) and space is O(amount).
Order matters or not
If 1 + 2 and 2 + 1 count as different payments, swap the loops: amounts outside, coins inside. The same cells give a different answer, so the loop order is part of the problem.
def count_orders(coins, amount): dp = [1] + [0] * amount for a in range(1, amount + 1): for c in coins: if c <= a: dp[a] += dp[a - c] return dp[amount]
print(count_orders([1, 2], 4))Example 5 · Sets against orders
coins = [1, 2, 3]for amount in range(1, 7): sets = [1] + [0] * amount for c in coins: for a in range(c, amount + 1): sets[a] += sets[a - c] orders = [1] + [0] * amount for a in range(1, amount + 1): orders[a] = sum(orders[a - c] for c in coins if c <= a) print(amount, sets[amount], orders[amount])1 1 1 2 2 2 3 3 4 4 4 7 5 5 13 6 7 24
What this code does
- The first number is the count of sets and the second the count of ordered payments. Orders are always at least as many.
- Only the loop order and the inner sum changed.
Example 6 · Fewest square numbers
n = 12INF = float("inf")dp = [0] + [INF] * nfor a in range(1, n + 1): k = 1 while k * k <= a: dp[a] = min(dp[a], dp[a - k * k] + 1) k += 1print(dp[n])3
What this code does
- This is coin change in disguise: the coins are the squares 1, 4, 9 and so on.
- 12 = 4 + 4 + 4, three squares.
For amount 4 with coins 1 and 2 there are 3 sets (1111, 112, 22) but 5 ordered ways (1111, 112, 121, 211, 22). Ask yourself which one the question wants before you write the loops.
Next step
Check your understanding
12 quick questions