目录

1. 题目描述

2. 解题分析

3. 代码实现 

1. 题目描述

        给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。你可以认为每种硬币的数量是无限的。

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

示例 2：
输入：coins = [2], amount = 3
输出：-1

示例 3：
输入：coins = [1], amount = 0
输出：0
 
提示：
1 <= coins.length <= 12
1 <= coins[i] <= 2^31 - 1
0 <= amount <= 10^4

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/coin-change
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题分析

        最少的硬币个数-->最短路径，可以考虑用广度优先搜索方法来求解。               

        以节点的状态表示（尚待换取的）金额。起始节点值为总金额amount。每条（有向）边代表所选取的硬币，经过边以后，到达的邻节点的值等于上一个节点值减去edge所代表的硬币值。由于每种硬币的数量是无限的，所以从每一个“节点”遍历其邻节点时，都可以考虑所有候选硬币。如此。。。以广度优先的方式进行搜索，直到找到第一个值为0的节点。

3. 代码实现 

import sys
import time
import random
from   collections import deque
from   typing import List

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        assert(amount >= 0)
        if amount == 0:
            return 0
        if amount < min(coins):
            return -1

        q = deque([amount])
        visited = set()
        layer = 1
        while q:            
            # print('layer = {0}, q.len = {1}'.format(layer,len(q)))
            n = len(q)
            for _ in range(n): # Traverse the current layer
                a = q.pop()
                if a in coins:
                    return layer
                # Add a's neighbours into q
                for c in coins:
                    b = a - c
                    if b > 0 and b not in visited:
                        visited.add(b)                        
                        q.appendleft(b)               
            layer = layer + 1
        return -1

if __name__ == '__main__':

    import time
    sln   = Solution()

    # testcase1
    coins = [1, 2, 5] 
    amount = 11
    print(sln.coinChange(coins, amount))

    # testcase2
    coins = [2] 
    amount = 3
    print(sln.coinChange(coins, amount))

    # testcase3
    coins = [1, 2, 5, 10, 20,50, 100] 
    amount = 1001
    tStart= time.time()
    print(sln.coinChange(coins, amount))
    tElapsed = time.time() - tStart        
    print('tElapsed = ', tElapsed, ' (sec)')

    # testcase3
    coins = [470,35,120,81,121]
    amount = 9825
    tStart= time.time()
    print(sln.coinChange(coins, amount))
    tElapsed = time.time() - tStart        
    print('tElapsed = ', tElapsed, ' (sec)')

        执行用时：424 ms, 在所有 Python3 提交中击败了99.17%的用户

        内存消耗：15.9 MB, 在所有 Python3 提交中击败了18.33%的用户

        通过测试用例：188 / 188

        一个巨大的教训是，visited用set()与用list有巨大的速度之差。一开始用list实现visited。。。超出时间限制。后来参考评论区的改用set,同一个超时的case在本机上执行的用时为1.77s vs 0.016s，竟然有100倍之巨！！！

        Lists are slightly faster than sets when you just want to iterate over the values.
        Sets, however, are significantly faster than lists if you want to check if an item is contained within it. They can only contain unique items though. It turns out tuples perform in almost exactly the same way as lists, except for their immutability.

        这道题目也可以用动态规划的方法。

回到本笔记系列总目录：笨牛慢耕的Leetcode解题笔记(动态更新。。。)https://chenxiaoyuan.blog.csdn.net/article/details/123040889