题目：

给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。
示例 1:
输入: coins = [1, 2, 5], amount = 11
输出: 3 
解释: 11 = 5 + 5 + 1
示例 2:
输入: coins = [2], amount = 3
输出: -1
说明:
你可以认为每种硬币的数量是无限的。

题目的理解：

看似很简单的题目，用了一天时间编写算法，但是结果是一直计算超时，!_!
参考了其他的解题思路，学习学习！

python实现

深度遍历(dfs)：

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        coins.sort(reverse=True)
        self.result = float('inf')

        def recycle(i, num, balance):
            if balance == 0:
                self.result = min(self.result, num)
                return

            for j in range(i, len(coins)):
                if (self.result - num) * coins[j] < balance:
                    break
                
                if balance < coins[j]:
                    continue

                recycle(j, num + 1, balance - coins[j])

        for i in range(len(coins)):
            recycle(i, 0, amount)

        return self.result if self.result != float('inf') else -1

思路是（1）将硬币从大到小排序 （2）依次进行堆放硬币，当达到指定值停止。（3）堆放过程中记录使用硬币的次数。（4）取出使用硬币最少的次数。（5）需要通过判断循环遍历是否有可能超过最小硬币数，来达到提高效率的方式。

广度遍历(bfs):

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        from collections import deque
        queue = deque([amount])
        step = 0
        visited = set()
        while queue:
            n = len(queue)
            for _ in range(n):
                tmp = queue.pop()
                if tmp == 0:
                    return step
                for coin in coins:
                    if tmp >= coin and tmp - coin not in visited:
                        visited.add(tmp - coin)
                        queue.appendleft(tmp - coin)
            step += 1
        return -1

思路：（1）目标金额进行每个硬币的计算。 （2）所有的值计算一次后得到一个层级的所有数。（3）继续计算下一层的数。（4）直到出现第一个0时，计算结束。

动态规划

1. 自底向上

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）根据提供的硬币，来计算1到amount每一个数需要的硬币个数。（2）amount数值大时，减去每一个硬币后转化为小数值来得到硬币个数。（3）减去的硬币数值就算使用了一个硬币。

2. 自顶向下

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）计算amount减去一个硬币后的值X，来获取X的硬币数。（2）一直递归返回值。

提交

好算法，还是不错的。

// END 多读书多写代码