322.md

解法一

• 1772ms
• 19.7%

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        n = len(coins)
        if n==0 or amount == -1: return -1
        state = [-1]*(amount+1)
        state[0] = 0
        for price in range(1, amount+1):
            for i in range(n):
                if price-coins[i] >= 0 and state[price-coins[i]] != -1:
                    if state[price] == -1 or state[price] > state[price-coins[i]]:
                        state[price] = state[price-coins[i]]+1
        return state[amount]

解法二

• 164ms
• 97%

class Solution:
    def __init__(self):
        self.res = float("inf")
        
    def coinChange(self, coins: List[int], amount: int) -> int:
        n = len(coins)
        if n==0 or amount == -1: return -1
        coins.sort(reverse=True)
        def dfs(start, remaining, count):
            if remaining==0:
                self.res = min(self.res, count)
            else:
                for i in range(start, n):
                    if coins[i] <= remaining and remaining < (self.res - count)*coins[i]:
                        dfs(i, remaining-coins[i], count+1)
        dfs(0, amount, 0)
        return self.res if self.res!= float("inf") else -1