思路：建一个动态数组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不能由这些零钱兑换。
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16int 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的全部内容，更多相关零钱兑换内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
发表评论 取消回复