概述
思路：建一个动态数组dp，大小为amount+1，dp里面的值初始化为amount+1。dp[i]表示总金额i最少可以用dp[i]的零钱兑换，
如果coins[j]比i小，那么总金额i可以由dp[i-conis[j]]再加上这枚零钱构成， dp[i]=min(dp[i],dp[i-coins[j]]+1)。如果dp[mount]=mount+1,则表示总金额mount不能由这些零钱兑换。
int coinChange(vector<int>& coins, int amount)
{
vector<int> dp(amount+1,amount+1);
dp[0]=0;
sort(coins.begin(),coins.end());
if(amount==0||coins.size()==0)
return 0;
for(int i=1;i<=amount;i++)
{
for(int j=0;j<coins.size()&&coins[j]<=i;j++)
dp[i]=min(dp[i],dp[i-coins[j]]+1);
}
if(dp[amount]==amount+1)
return -1;
else return dp[amount];
}
最后
以上就是瘦瘦钢笔为你收集整理的零钱兑换 leetcode的全部内容，希望文章能够帮你解决零钱兑换 leetcode所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
发表评论 取消回复