难度：中等

题目内容：

给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。

示例 1:

输入: coins = [1, 2, 5], amount = 11
输出: 3
解释: 11 = 5 + 5 + 1
示例 2:

输入: coins = [2], amount = 3
输出: -1
说明:
你可以认为每种硬币的数量是无限的。

题解：

这个题我第一眼就想到递归，让使用的硬币面值最大值越来越小

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        if amount == 0:
            return 0
        if amount < coins[-1]:
            for i in range(len(coins)-1,-1,-1):
                if amount == coins[i]:
                    return 1
                if amount > coins[i]:
                    break
            coins = coins[0:i+1]
        if amount == coins[-1]:
            return 1
        if len(coins) == 1 and amount > coins[-1]:
            if amount%coins[-1] == 0:
                return amount//coins[-1]
        if len(coins) <= 1:
            return -1

        else:
            r = -1
            k = 1
            while amount > k*coins[-1]:
                n = self.coinChange(coins,amount - k * coins[-1])
                if not n == -1:
                    if r > n or r == -1:
                        r = n + k
                k += 1
            return r

但是很不幸啊，超时了😂
来看看leetcode的官方解法吧😂
就发现果然我还是很不擅长动态规划噢。。。

leetcode解法1

image.png
image.png

在上面的递归树中，我们可以看到许多子问题被多次计算。例如， F(1)F(1) 被计算了 1313 次。为了避免重复的计算，我们将每个子问题的答案存在一个数组中进行记忆化，如果下次还要计算这个问题的值直接从数组中取出返回即可，这样能保证每个子问题最多只被计算一次。

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/coin-change/solution/322-ling-qian-dui-huan-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

import functools

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        @functools.lru_cache(amount)
        def dp(rem):
            if rem < 0: return -1
            if rem == 0: return 0
            mini = int(1e9)
            for coin in self.coins:
                res = dp(rem - coin)
                if res >= 0 and res < mini:
                    mini = res + 1
            return mini if mini < int(1e9) else -1

        self.coins = coins
        if amount < 1: return 0
        return dp(amount)

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/coin-change/solution/322-ling-qian-dui-huan-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

image.png

leetcode解法2：

image.png
image.png

复杂度分析

时间复杂度：O(Sn)O(Sn)，其中 SS 是金额，nn 是面额数。我们一共需要计算 O(S)O(S) 个状态，SS 为题目所给的总金额。对于每个状态，每次需要枚举 nn 个面额来转移状态，所以一共需要 O(Sn)O(Sn) 的时间复杂度。
空间复杂度：O(S)O(S)。DP 数组需要开长度为总金额 SS 的空间。

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        dp = [float('inf')] * (amount + 1)
        dp[0] = 0
        
        for coin in coins:
            for x in range(coin, amount + 1):
                dp[x] = min(dp[x], dp[x - coin] + 1)
        return dp[amount] if dp[amount] != float('inf') else -1 

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/coin-change/solution/322-ling-qian-dui-huan-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。