You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.
You may assume that you have an infinite number of each kind of coin.
Example 1:
Input: coins = [1,2,5], amount = 11 Output: 3 Explanation: 11 = 5 + 5 + 1
Example 2:
Input: coins = [2], amount = 3 Output: -1
Example 3:
Input: coins = [1], amount = 0 Output: 0
Example 4:
Input: coins = [1], amount = 1 Output: 1
Example 5:
Input: coins = [1], amount = 2 Output: 2
Constraints:
1 <= coins.length <= 121 <= coins[i] <= 231 - 10 <= amount <= 104
PS: see problem 518 for variation of the problem (number of combinations instead of smallest number of coins)
Source
def change_coins(coins, amount):
"""Naive recursive DFS using memoization. Doesn't require to sort coin"""
def dfs(remain):
nonlocal change, coins
if remain in change:
return change[remain]
if remain < 0:
return float('inf')
change[remain] = min([dfs(remain-coin) for coin in coins]) + 1
return change[remain]
if not amount:
return 0
change = {0: 0, **{coin: 1 for coin in coins}}
dfs(amount)
return -1 if change[amount] == float('inf') else change[amount]
def change_coins(coins, amount):
"""alternative version of above solution (faster but requires sorting coins)."""
def dfs(remain):
nonlocal change, coins
if remain in change:
return change[remain]
change[remain] = float("inf")
for coin in coins:
if coin > remain:
break # exit when coins get too big
nb_coins = 1 + dfs(remain - coin)
if nb_coins < change[remain]:
change[remain] = nb_coins
return change[remain]
if not amount:
return 0
coins.sort()
change = {0: 0, **{coin: 1 for coin in coins}}
dfs(amount)
return -1 if change[amount] == float('inf') else change[amount]
def change_coins(coins, amount):
"""Recursive DFS using branch and bound to eliminate not interesting solutions early on.
Starts as a greedy approach, but keeps on as long as better options exist
No memoization used
"""
def dfs(remain, start=0, coins_so_far=0):
nonlocal coins, result
if not remain and coins_so_far < result:
result = coins_so_far
return
for i, coin in enumerate(coins[start:], start):
coins_margin = result - coins_so_far # how many coins can we use if we want to do better
max_amount = coin * coins_margin # maximum amount possible with biggest (current) coin
if coin <= remain < max_amount: # if leftover coins aren't too big nor too small
dfs(remain-coin, i, coins_so_far+1)
if not amount:
return 0
coins.sort(reverse=True)
result = float('inf')
dfs(amount)
return -1 if result == float("inf") else result
def change_coins(coins, amount):
"""(bit) faster version of above solution using different variables.
"""
def dfs(remain, start=0, coins_so_far=0):
nonlocal coins, result
if not remain and coins_so_far < result:
result = coins_so_far
return
for i, coin in enumerate(coins[start:], start):
min_nb_coins_extra = remain // coin # DIFF HERE
min_nb_coins = coins_so_far + min_nb_coins_extra # DIFF HERE
if coins_so_far < min_nb_coins < result: # DIFF HERE
dfs(remain-coin, i, coins_so_far+1)
if not amount:
return 0
coins.sort(reverse=True)
result = float('inf')
dfs(amount)
return -1 if result == float("inf") else result
def change_coins(coins, amount):
"""Yet another slightly faster recursive DFS using branch and bound version
"""
def dfs(remain, start=0, coins_so_far=0):
nonlocal coins, result
lower_bound, left = divmod(remain, coins[start]) # divmod(x,y) = (x//y, x%y)
min_nb_coins = lower_bound + coins_so_far
if min_nb_coins >= result: # if what we would need is larger than current result
return
if left == 0: # but if we can get exactly the amount needed with less coins
result = min_nb_coins
return
if start == len(coins) - 1: # if we explored everything
return
for extra_nb_coins in range(lower_bound, -1, -1):
new_remain = remain - (coins[start] * extra_nb_coins)
dfs(new_remain, start + 1, coins_so_far + extra_nb_coins)
if not amount:
return 0
coins.sort(reverse=True)
result = float('inf')
dfs(amount)
return -1 if result == float('inf') else result
def change_coins(coins, amount):
"""fastest variation of above solutions"""
def dfs(remain, start=0, coins_so_far=0):
nonlocal coins, result
if start == len(coins): # DIFF HERE (n and not n-1)
return
lower_bound, left = divmod(remain, coins[start]) # divmod(x,y) = (x//y, x%y)
min_nb_coins = lower_bound + coins_so_far
if left == 0 and min_nb_coins < result:
result = min_nb_coins
return
if min_nb_coins + 1 >= result: # DIFF HERE (+1)
return
for extra_nb_coins in range(lower_bound, -1, -1):
new_remain = remain - (coins[start] * extra_nb_coins)
dfs(new_remain, start + 1, coins_so_far + extra_nb_coins)
if not amount:
return 0
coins.sort(reverse=True)
result = float("inf")
dfs(amount)
return -1 if result == float('inf') else result
def change_coins(coins, amount):
"""almost as fast as above, but much clearer to understand
"""
def dfs(remain, start=0, coins_so_far=0):
nonlocal coins, result
lower_bound, left = divmod(remain, coins[start])
if left:
lower_bound += 1
if lower_bound + coins_so_far >= result: # if the result from this branch is not interesting
return
if remain in coins[start:] and coins_so_far < result: # if one of the available coins can do the job
result = coins_so_far+1
return
if coins[start] < remain: # option 1: use the biggest coin
dfs(remain-coins[start], start, coins_so_far+1)
if start < len(coins)-1: # option 2: use the 2nd biggest if possible
dfs(remain, start+1, coins_so_far)
if not amount:
return 0
coins.sort(reverse=True)
result = float('inf')
dfs(amount)
return -1 if result == float('inf') else result
coins = [1,2,5]
amount = 11
change_coins(coins, amount)
3
coins = [1,2,5]
amount = 100
change_coins(coins, amount)
20
Solve it both recursively and iteratively.
def change_coins(coins, amount):
"""Naive Dynamic Programming solution
Note that this is a complete Knapsack problem:
- amount = capacity of the "Knapsack"
- coins = value of each item you can put into the Knapsack
- you can take 0 or many coins
- for each coin the cost is constant 1
so the question is to find minimum cost to fill the Knapsack
"""
change = [0]*(amount+1)
for val in range(1, amount+1):
minimum = float("inf")
for coin in coins:
if val >= coin and change[val-coin] < minimum:
minimum = change[val-coin]
change[val] = 1+minimum
return -1 if change[-1] == float("inf") else change[-1]
def change_coins(coins, amount):
"""Dynamic Programming solution with sorted coins to break loop"""
coins.sort()
change = [0]*(amount+1)
for val in range(1, amount + 1):
minimum = float("inf")
for coin in coins:
if coin > val:
break # exit when coins get too big
if change[val-coin] < minimum:
minimum = change[val - coin]
change[val] = minimum+1
return -1 if change[amount] == float('inf') else change[amount]
def change_coins(coins, amount):
"""iterative DFS using branch and bound """
if not amount:
return 0
coins.sort(reverse=True)
result = float("inf")
stack = [(amount, 0, 0)]
while stack:
remain, start, coins_so_far = stack.pop()
if not remain and coins_so_far < result:
result = coins_so_far
continue
for i in reversed(range(start, len(coins))): # why reversed ???
coins_margin = result - coins_so_far
max_amount = coins[i] * coins_margin
if coins[i] <= remain < max_amount:
stack += (remain-coins[i], i, coins_so_far + 1),
return -1 if result == float("inf") else result
def change_coins(coins, amount):
"""Same as above but using different variables"""
if not amount:
return 0
coins.sort(reverse=True)
result = float("inf")
stack = [(amount, 0, 0)]
while stack:
remain, start, coins_so_far = stack.pop()
if not remain and coins_so_far < result:
result = coins_so_far
continue
for i in reversed(range(start, len(coins))):
lower_bound = remain // coins[i] # DIFF HERE
min_nb_coins = coins_so_far + lower_bound # DIFF HERE
if coins_so_far < min_nb_coins < result: # DIFF HERE
stack += (remain-coins[i], i, coins_so_far + 1),
return -1 if result == float("inf") else result