leetcode 322 广度优先搜索解决，注意剪枝

给你一个整数数组 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] <= 231 - 1 0 <= amount <= 104

通过次数435,420提交次数955,940

题解：因为题目要返回最小次数，一般思路有动态规划和BFS，这里采用BFS。

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        //sort(coins.begin(),coins.end());
        vector<int> visited(amount+1,0);        //这里增加一个剪枝
        if(amount==0)
            return 0;
        queue<int> qpos;
        qpos.push(amount);
        int times = 0;
        while(!qpos.empty())
        {
            times++;//需要的时间
            int size = qpos.size();
            while (size-- > 0) 
            {
                int temposcur;
                temposcur = qpos.front();
                qpos.pop();
                for(int i = 0; i < coins.size(); i++)
                {
                    if(temposcur-coins[i]>0 && visited[temposcur-coins[i]]==0)
                    {
                        int pos=temposcur-coins[i];
                        visited[pos]=1;
                        qpos.push(pos);
                    }
                    if(temposcur-coins[i]==0)
                        return times;
                }
            }
        }
        return -1;
    }
};

执行结果：

通过

显示详情

添加备注

执行用时：76 ms, 在所有 C++ 提交中击败了59.83%的用户

内存消耗：17.8 MB, 在所有 C++ 提交中击败了10.66%的用户

通过测试用例：188 / 188