思路：建一个动态数组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的全部内容，更多相关零钱兑换内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
发表评论 取消回复