本题属于完全背包问题，但要求最少的硬币个数。于是设定dp数组的含义dp[i]:总金额为i时，能凑成i的最少硬币个数。 需要注意初始化dp数组时，除0以外的其他地方需要初始化为INT_MAX以保证在递推过程中能被正确的覆盖。
代码如下：文章来源：https://www.toymoban.com/news/detail-653580.html
class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
vector<int> dp(amount+1,INT_MAX);
dp[0] = 0;
for(int i=0; i<coins.size(); i++)
{
for(int j=coins[i]; j<=amount; j++)
{
//跳过当dp[j-coins[i]]为初始值的情况
if(dp[j-coins[i]] != INT_MAX)
{
dp[j] = min(dp[j] , dp[j-coins[i]]+1);
}
}
}
if(dp[amount] == INT_MAX) return -1;
else return dp[amount];
}
};ps：本题由于求得是硬币最小个数，那么钱币有顺序和没有顺序都可以，都不影响钱币的最小个数。所以本题并不强调集合是组合还是排列，先遍历物品和背包都可以！文章来源地址https://www.toymoban.com/news/detail-653580.html
到了这里，关于leetcode 322. 零钱兑换的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
