零钱兑换
给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。
你可以认为每种硬币的数量是无限的。
示例:
输入：coins = [1, 2, 5], amount = 11
输出：3
解释：11 = 5 + 5 + 1
思路
解法一：
本题与279.完全平方数解题方法一致，都是求最小问题，很容易想到 BFS 。
- 将
amount看作根节点，构造多叉树，其节点为平方数； - 每次从大到小进行取值，若差值为
0,则证明找到最短路径； - 使用 set 消除同一层中相等的数重复计算情况。
class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
if (amount == 0) return 0;
unordered_set<int> visited; //记录访问过的节点值
queue<int> q;
int step = 0;
q.push(amount);
while (q.size()) {
int len = q.size();
step++;
while (len--) {
int j = q.front();
q.pop();
for (int coin : coins) { // 遍历硬币
int m = j - coin;
if (m == 0) { // 如果凑齐，直接返回
return step;
}
if (m < 0 ) {
continue;
}
if (!visited.count(m)) { // 若没有记录过该值，加入队列，消除同一层中相同的数
visited.insert(m);
q.push(m);
}
}
}
}
return -1;
}
};