原题出处：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，那就不用选了
以及对于“走过”路径的排除，用一个数组记录已经判断过的金额数量

2025-06-11 start:

class Solution {
    public int coinChange(int[] coins, int amount) {
        if (amount == 0) {
            return 0;
        }
        int[] dp = new int[amount+1];
        
        Arrays.fill(dp,amount+1);
        dp[0] = 0;
        for (int i = 1 ; i < amount+1; i++) {
            for (int coin : coins) {
                if (i>=coin) {
                    dp[i] = Math.min(dp[i],dp[i-coin]+1);
                }
            }
        }
        return dp[amount] > amount ? -1 : dp[amount];
    }
}

思路：动态规划

end