|
| 1 | +''' |
| 2 | +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. |
| 3 | + |
| 4 | +Example 1: |
| 5 | +coins = [1, 2, 5], amount = 11 |
| 6 | +return 3 (11 = 5 + 5 + 1) |
| 7 | + |
| 8 | +Example 2: |
| 9 | +coins = [2], amount = 3 |
| 10 | +return -1. |
| 11 | + |
| 12 | +Note: |
| 13 | +You may assume that you have an infinite number of each kind of coin. |
| 14 | +''' |
| 15 | +class Solution(object): |
| 16 | + def coinChange(self, coins, amount): |
| 17 | + #corner cases |
| 18 | + if amount == 0: |
| 19 | + return 0 |
| 20 | + if len(coins) == 1 and coins[0] > amount: |
| 21 | + return -1 |
| 22 | + dp = [-1 for i in range(amount + 1)] |
| 23 | + for i in range(1, amount + 1): |
| 24 | + # if the value matches the coin |
| 25 | + if i in coins: |
| 26 | + dp[i] = 1 |
| 27 | + else: |
| 28 | + minV = sys.maxsize |
| 29 | + # since the size of coins are much less than the amount, |
| 30 | + # we check if for every coin there could be a solution and find the minimum of that |
| 31 | + for j in coins: |
| 32 | + remain = i - j |
| 33 | + # -1 means there is no solution, so we don't need to check if dp[i] is -1 |
| 34 | + if remain > 0 and dp[remain] != -1: |
| 35 | + minV = min(minV, dp[remain]) |
| 36 | + if minV ==sys.maxsize: |
| 37 | + dp[i] = -1 |
| 38 | + else: |
| 39 | + dp[i] = minV + 1 |
| 40 | + return dp[-1] |
| 41 | + |