Leetcode 322. Coin Change (Python)

Related Topic

Dynamic-Programming.

Description

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.

Sample I/O

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

Methodology

This question solved by Dynamic Programming. It is similar with question 279. Perfect Squares. The only difference is if that amount of money cannot be made up by any combination of the coins, return -1 and the perfect square question can always made up by any combination of square.

This question can be solved by Dynamic Programming. However, dp is not the best solution.

If the amount is made up by coins, then the most number of coins will no more than the amount itself. Here is a tricky thing, some people may init a dp list with value all equal to the amount itself and think if the final will be smaller or equal to itself. This is only right if there must be a $1 coin. That is the difference between perfect square I mentioned above. For this question, there could be 1 coin and it smaller than amount but not divideable by the amout, say amount = 7, coin = [3]. After comparion, we can find the fewest number of coins is 7, but actually it should return -1 because the 3 is not dividable by 7.

Otherwise the question will just be same as perfect square qustion.

Base case:

We create dp list and init each value to amount+1. Init 0 index as 0 because the number of amount for 0 is 0.

We are given a list of coins.

Pattern

Iterate the value if the value is smaller than the coin, we skip the iteration to next. Otherwise, we give the compare amount+1 with the number of amount - coin plus 1, update the current value to the smallest.

Code

def coinChange(self, coins: List[int], amount: int) -> int:
        new_coins = sorted(coins)
        dp = [amount for _ in range(amount+1)]
        dp[0] = 0
        #dp[11]=5 means 5 coins will get 11 
        for each_amo in range(1,amount+1):
            for coin in new_coins:
                if coin <= each_amo:
                    dp[each_amo] = min(dp[each_amo], 1+dp[each_amo-coin])
                else:
                    break
        return dp[amount] if dp[amount]<=amount else -1

BigO

We iterate all dp array, it will cost O(n), inside the iteration, we need to iterate the coins which is O(m) So the total time complexity is O(nm)