:type coins: List[int] :type amount: int :rtype: int
(self, coins, amount)
| 51 | """ |
| 52 | class Solution(object): |
| 53 | def coinChange(self, coins, amount): |
| 54 | """ |
| 55 | :type coins: List[int] |
| 56 | :type amount: int |
| 57 | :rtype: int |
| 58 | """ |
| 59 | dp = {0: 0} |
| 60 | mins = min(coins) |
| 61 | inf = float('inf') |
| 62 | for i in range(mins, amount+1): |
| 63 | dp[i] = min((dp.get(i-j, inf)+1 for j in coins)) |
| 64 | |
| 65 | # for i in coins: |
| 66 | # for j in range(i, amount+1): |
| 67 | # dp[j] = min(dp.get(j, inf), dp.get(j-i, inf)+1) |
| 68 | |
| 69 | # for i in range(mins, amount+1): |
| 70 | # dp[i] = min((dp.get(i-j, inf)+1 for j in coins)) |
| 71 | # temp = [] |
| 72 | # for j in coins: |
| 73 | # temp.append(dp.get(i-j, inf)+1) |
| 74 | # dp[i] = min(temp) |
| 75 | |
| 76 | if dp.get(amount) == inf: |
| 77 | return -1 |
| 78 | return dp.get(amount, -1) |
| 79 | |
| 80 | # coins = set(coins) |
| 81 | # dp = [(0, 0)] |
| 82 | # for i in range(1, amount+1): |
| 83 | # temp = [] |
| 84 | # for j in range(len(dp)-1, -1, -1): |
| 85 | # j = dp[j] |
| 86 | # if i - j[1] in coins: |
| 87 | # temp.append((j[0]+1, i)) |
| 88 | # if temp: |
| 89 | # dp.append(min(temp, key=lambda x: x[0])) |
| 90 | # print(dp) |
| 91 | # if dp[-1][1] == amount: |
| 92 | # return dp[-1][0] |
| 93 | |
| 94 | # return -1 |
| 95 | |
| 96 | a = Solution() |
| 97 |