Coin Change
DSA · Dynamic Programming
Theory
Coin change has two classic forms. Minimum coins: dp[a] is the fewest coins making amount a, computed as 1 + min(dp[a - coin]) over all coins. Number of ways: dp[a] counts combinations, adding dp[a - coin] while looping over coins on the outside so each combination is counted once. Both run in O(amount × number of coins) and work for any coin system, unlike greedy.
Why we use it
It shows how DP fixes problems where greedy fails and is a very common interview question.
When to use it
Use it for making change, counting ways to reach a score, unbounded knapsack and resource combination problems.
How it works
- dp[0] = 0, others infinity
- For amount a = 1..target
- For each coin c <= a: dp[a] = min(dp[a], dp[a - c] + 1)
- dp[target] is infinity? Yes: Return -1. No: Return dp[target].
Syntax
Minimum coins:
dp = [0] + [inf] * amount
for a in 1..amount: dp[a] = min(dp[a-c] + 1 for c in coins if c <= a)
Number of ways:
ways = [1] + [0] * amount
for c in coins: for a in c..amount: ways[a] += ways[a-c]Example
def min_coins(coins, amount):
dp = [0] + [float("inf")] * amount
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
return dp[amount] if dp[amount] != float("inf") else -1
def count_ways(coins, amount):
ways = [1] + [0] * amount
for c in coins:
for a in range(c, amount + 1):
ways[a] += ways[a - c]
return ways[amount]
print("Min coins for 6 with [1,3,4]:", min_coins([1, 3, 4], 6))
print("Min coins for 11 with [2]:", min_coins([2], 11))
print("Ways to make 10 with [1,2,5]:", count_ways([1, 2, 5], 10))Key points
- Minimum coins vs number of ways
- Works for any coin set
- Outer loop over coins counts combinations
- O(amount × coins) time