I am looking at a particular solution that was given for LeetCode problem 322. Coin Change :
You are given an integer array
coins
representing coins of different denominations and an integeramount
representing a total amount of money.Return 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.
Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
@cache
def dfs(rem):
if rem == 0:
return 0
min_cost = float('inf')
for coin in coins:
if rem / coin > min_cost: #???????????
break
if rem - coin >= 0:
min_cost = min(min_cost, dfs(rem - coin) + 1)
return min_cost
coins.sort(reverse=True)
res = dfs(amount)
return res if res != float('inf') else -1
The code is significantly faster if I use the optimization step I have marked with #???????????
in the code above. Why does that optimization step make sense? I understand the list is reverse sorted, but it is not like we are using only the coin in that iteration or the lower denominations to make up the amount. We are using the larger denominations as well I think.
This is given in the line
if rem - coin >= 0:
min_cost = min(min_cost, dfs(rem - coin) + 1)
Why is dfs(rem-coin) + 1
always going to be greater than rem / coin
?
This optimization is not correct when coins
is not sorted (though it would be fine if break
were replaced with continue
).
That line essentially states that if even taking as many of the current denomination as possible uses up more coins that the previously found lowest value, then there is no need to try it. The only way to improve upon the previous optimal value is to use a coin with a larger denomination at some point. This optimization prevents dfs
from using the same coins a substantial amount of times but in a different order.
Note that one can write a simpler solution with bottom-up dynamic programming.
class Solution:
def coinChange(self, coins: list[int], amount: int) -> int:
from math import inf
minCoins = [0] + [inf] * amount
for coin in coins:
for c in range(coin, amount + 1):
minCoins[c] = min(minCoins[c], minCoins[c - coin] + 1)
return -1 if minCoins[-1] == inf else minCoins[-1]