原题出处：https://leetcode.cn/leetbook/read/top-interview-questions-medium/xvf0kh/

解法一：

import heapq
class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        que = [(0,0)]
        heap_found = [False]*(amount+1)
        while que:
            step,num = heapq.heappop(que)
            if num == amount:
                return step
            for c in coins:
                if num + c <= amount and not heap_found[num + c]:
                    heapq.heappush(que,(step + 1,num+c))
                    heap_found[num + c] = True
        if not heap_found[amount]:
            step = -1
        return step

思路：

广度优先

利用优先队列，队列内保存(step,cur)
其中step是当前硬币数,cur是当前金额
初始队列为
que = [(0,0)]

每次都从coins数组里面选择加入
由于是按最小步数排序的，所有当满足要求时一定是最少的硬币数量，搜索顺序如下。

但是有一个限界条件：如果当前金额+要选择的金额大于amount，那就不用选了
以及对于“走过”路径的排除，用一个数组记录已经判断过的金额数量