LC-322. 零钱兑换
2024-08-26 06:22:22
322. 零钱兑换
给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。
你可以认为每种硬币的数量是无限的。
示例 1：
输入：coins = [1, 2, 5], amount = 11
输出：3
解释：11 = 5 + 5 + 1
示例 2：
输入：coins = [2], amount = 3
输出：-1
解析:
经典多重背包问题,对于当前的背包大小,遍历每一个背包重量,得到前面重量需要的最小值.
class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
//多重背包
int n = coins.size();
vector<int> dp(amount + 1,INT_MAX);
dp[0] = 0;
for(int i = 0; i <= amount; i++){
for(int j = 0; j < n; j++){
//如果前一个重量可以拼出来
if(i >= coins[j]){
if(dp[i - coins[j]] != INT_MAX)
//转移,当前所需的个数和拿完第j个需要个数最小值
dp[i] = min(dp[i], dp[i - coins[j]] + 1);
}
}
}
return dp[amount] == INT_MAX ? -1 : dp[amount];
}
};
最新文章
- json转类
- 百度echart使用心得，百度图表。
- FTP的20、21端口，工作模式
- mormot 数据集转换为JSON字串
- CUBRID学习笔记 22 插入数据
- [工作积累] bitfield
- c++各种排序
- 卸载sqlserver数据库参考
- UML学习-状态图
- Java学习——何为JNDI
- MyEclipse使用总结——MyEclipse文件查找技巧
- Android 仿映客直播间给主播发送礼物（实现连击效果）
- JS数组根据属性来实现排序
- R语言︱构造新序列
- linux服务器中毒可疑进程sfewfesfs CPU80%
- seo优化做起来不是哪么简单，其实需要的是思维
- web优化（二）
- SQL优化方法：
- PYTHON语言之常用内置函数
- 换上 SansForgetica-Regular 字体,增加记忆能力