企业官网建设流程全解析

给定不同面额的硬币coins和一个总金额amount，请计算凑成总金额所需的最少硬币个数。

如果没有任何一种硬币组合能组成总金额，输出-1。

每种硬币的数量是无限的。

输入描述

第一行输入一个整数n，表示硬币种类数。

第二行输入n个整数，表示硬币面额。

第三行输入一个整数amount，表示总金额。

输出描述

输出最少硬币个数，若无法凑成则输出-1。

示例 1

输入

text

3 1 2 5 11

输出

text

3

说明

11 = 5 + 5 + 1，共 3 枚硬币。

C++ 解法

cpp

#include <bits/stdc++.h> using namespace std; int main() { int n; cin >> n; vector<int> coins(n); for (int i = 0; i < n; i++) cin >> coins[i]; int amount; cin >> amount; vector<int> dp(amount + 1, INT_MAX); dp[0] = 0; for (int i = 1; i <= amount; i++) { for (int coin : coins) { if (i >= coin && dp[i - coin] != INT_MAX) { dp[i] = min(dp[i], dp[i - coin] + 1); } } } cout << (dp[amount] == INT_MAX ? -1 : dp[amount]) << endl; return 0; }