A22785. 硬币
填空题
较易
知识点
题目描述
硬币
题目描述
可以使用任意数量的 a元硬币、b 元硬币和 c 元硬币。请找出恰好凑出 n 元所需的最小硬币总数。若无法凑出，则输出 -1。
输入格式
第一行，整数 n；
第二行，三个整数表示 a、b、c。
输出格式
输出最小硬币总数（若无法凑出则输出 -1）。
输入样例#1
100
20 40 50输出样例#1
2输入样例#2
99
1 5 10输出样例#2
14参考答案
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
int a, b, c;
cin >> a >> b >> c;
int coins[3] = {a, b, c}; // 存储三种硬币面值
// 定义dp数组：dp[i]表示凑i元的最小硬币数
// 用n+1作为"不可达"的标记（因为最多需要n枚1元硬币，n+1一定大于可能的最大值）
int* dp = new int[n + 1];
for (int i = 0; i <= n; ++i) {
dp[i] = n + 1; // 初始化所有金额为"不可达"
}
dp[0] = 0; // 基准条件：0元需要0枚硬币
// 填充dp数组
for (int i = 1; i <= n; ++i) {
for (int j = 0; j < 3; ++j) { // 遍历三种硬币
int coin = coins[j];
// 若当前金额i大于等于硬币面值，且"i-coin"金额可达，则尝试更新
if (i >= coin && dp[i - coin] + 1 < dp[i]) {
dp[i] = dp[i - coin] + 1;
}
}
}
// 输出结果：若dp[n]仍为n+1，说明无法凑出，否则输出最小硬币数
cout << (dp[n] > n ? -1 : dp[n]) << endl;
// 释放动态分配的内存
delete[] dp;
return 0;
}
上一题
下一题