动态规划：零钱兑换_动态规划换零钱

最基本的解法（python）：

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        n = len(coins)
        f = [0] + [float('inf')]*amount
        k = amount + 1 
        for i in range(1,k):
            for j in range(n):
                if i >= coins[j] and f[i - coins[j]] != float('inf') and (f[i - coins[j]] + 1) < f[i]:
                    f[i] = f[i - coins[j]] + 1
        if f[amount] == float('inf'):
            return -1
        else:
            return f[amount]
1
2
3
4
5
6
7
8
9
10
11
12
13

方法二（自底而上，参考LeetCode评论写法）：

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        # 自底向上
        # dp[i] 表示金额为i需要最少的硬币
        # dp[i] = min(dp[i], dp[i - coins[j]]) j所有硬币
        
        dp = [float("inf")] * (amount + 1)
        dp[0] = 0
        for i in range(1, amount + 1):
            dp[i] = min(dp[i - c] if i - c >= 0 else float("inf") for c in coins ) + 1
        return dp[-1] if dp[-1] != float("inf") else -1
1
2
3
4
5
6
7
8
9
10
11

方法三（自顶向下，参考LeetCode评论写法）：

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        import functools
        @functools.lru_cache(None)
        def helper(amount):
            if amount == 0:
                return 0
            return min(helper(amount - c) if amount - c >= 0 else float("inf") for c in coins) + 1
        res = helper(amount)
        return res if res != float("inf") else -1
1
2
3
4
5
6
7
8
9
10