Coin Change

You are given a list of coin denominations and a target amount. Return the minimum number of coins needed to make exactly that amount, assuming an unlimited supply of each coin. If the amount cannot be formed, return -1.

Example#

For coins = [1, 2, 5] and amount = 11, the fewest coins is 3 (5 + 5 + 1). For coins = [2] and amount = 3, no combination works, so return -1.

Brute force note#

Greedily grabbing the largest coin each time is wrong: for coins [1, 3, 4] and amount 6, greedy gives 4+1+1 (three coins) but the optimum is 3+3 (two coins). Exhaustive recursion over every coin choice is exponential.

Optimal approach#

Let dp[a] be the minimum coins needed to make amount a. Start dp[0] = 0 and everything else as infinity. For each amount from 1 to the target, try every coin c: if c is at most a, then dp[a] could improve to dp[a - c] + 1. Take the minimum over all coins. The final answer is dp[amount], or -1 if it stayed infinite.

 1def coin_change(coins, amount):
 2    inf = amount + 1
 3    dp = [0] + [inf] * amount
 4    for a in range(1, amount + 1):
 5        for c in coins:
 6            if c <= a:
 7                dp[a] = min(dp[a], dp[a - c] + 1)
 8    return dp[amount] if dp[amount] != inf else -1
 9
10
11print(coin_change([1, 2, 5], 11))  # 3
12print(coin_change([2], 3))         # -1
13print(coin_change([1, 3, 4], 6))   # 2

Complexity#

Time is O(amount times number_of_coins): each amount tries every coin once. Space is O(amount) for the dp table.

This is the standard unbounded-knapsack style DP. Study the table-filling technique on the dynamic programming topic page, then continue through the 60-day curriculum.