algorithmdata-structuresdynamic-programming

Minimum number of coins needed for amount with infinite coins available. Understanding the optimization


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 integer amount 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?


Solution

  • 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]