#P4092. 零钱兑换
-
ID: 2329
Tried: 124
Accepted: 35
Difficulty: 8
-
算法标签>动态规划
零钱兑换
题目内容
给你一个整数数组 coins，表示不同面额的硬币；以及一个整数 amount ，表示总金额。
计算并返回可以凑成总金额所需的最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 −1 。
你可以认为每种硬币的数量是无限的。
输入描述
第一行一个数组coins 第二行一个整数amount
输出描述
一个整数表示可以凑成总金额所需的最少的硬币个数
样例1
输入
1 2 5
11
输出
3
说明
11=5+5+1
样例2
输入
2
3
输出
-1
样例3
输入
1
0
输出
0
提示：
- 1<=coins.length<=12
- 1<=coins[i]<=231−1
- 0<=amount<=104
题解
题面描述
给定一个整数数组 coins 表示不同面额的硬币，以及一个整数 amount 表示总金额。要求计算并返回凑成总金额所需的最少的硬币个数，如果没有任何一种硬币组合能组成总金额，则返回 −1。可以认为每种硬币的数量是无限的。
思路
本题采用 动态规划 的方法。
- 定义数组 dp，其中 dp[i] 表示凑成金额 i 所需的最少硬币个数。
- 初始化时：
- dp[0]=0（凑成 0 金额不需要任何硬币）
- 其他 dp[i] 初始化为一个较大值（例如 amount+1，表示不可达）
- 状态转移：
对于每个金额 i，遍历所有硬币面额 coin，如果 i≥coin，则更新dp[i]=min(dp[i], dp[i−coin]+1) - 最终若 dp[amount] 仍大于 amount（说明无法组成该金额），则输出 −1；否则输出 dp[amount]。
代码分析
- 动态规划数组初始化：
数组 dp 的大小为 amount+1，其中 dp[0]=0，其他位置初始化为一个不可能达到的数值（例如 amount+1）。 - 状态转移：
对于每个金额 i，遍历所有硬币面额，如果当前金额大于等于硬币面额，则尝试使用该硬币，看能否达到更优的方案。 - 时间复杂度：
外层循环迭代 amount 次，内层循环迭代 coins 数量，整体时间复杂度为 O(amount×coins.length)，满足题目给出的约束。
C++
#include <iostream>
#include <sstream>
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
// 函数功能：返回凑成总金额 amount 所需的最少硬币个数，若无法凑成则返回 -1
int coinChange(vector<int>& coins, int amount) {
// 初始化 dp 数组，大小为 amount + 1，初始值为 amount + 1（不可达状态）
vector<int> dp(amount + 1, amount + 1);
dp[0] = 0; // 金额 0 不需要任何硬币
// 遍历所有金额
for (int i = 1; i <= amount; i++) {
// 遍历所有硬币面额
for (int coin : coins) {
if (i >= coin) {
dp[i] = min(dp[i], dp[i - coin] + 1);
}
}
}
// 如果 dp[amount] 大于 amount，说明无法凑成该金额
return dp[amount] > amount ? -1 : dp[amount];
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
string line;
// 读取第一行硬币数组（用空格分隔）
getline(cin, line);
istringstream iss(line);
vector<int> coins;
int value;
while (iss >> value) {
coins.push_back(value);
}
// 读取第二行金额
int amount;
cin >> amount;
Solution solution;
int result = solution.coinChange(coins, amount);
cout << result << "\n";
return 0;
}
Python
# 定义一个 Solution 类，包含解决硬币问题的函数
class Solution:
def coinChange(self, coins, amount):
# 初始化 dp 数组，大小为 amount+1，初始值为 amount+1（表示不可达）
dp = [amount + 1] * (amount + 1)
dp[0] = 0 # 金额 0 不需要任何硬币
# 遍历所有金额
for i in range(1, amount + 1):
# 遍历每个硬币面额
for coin in coins:
if i >= coin:
dp[i] = min(dp[i], dp[i - coin] + 1)
# 如果 dp[amount] 依然大于 amount，说明无法凑成该金额
return -1 if dp[amount] > amount else dp[amount]
if __name__ == "__main__":
import sys
# 读取第一行硬币数组（以空格分隔）
line = sys.stdin.readline().strip()
coins = list(map(int, line.split()))
# 读取第二行金额
amount = int(sys.stdin.readline().strip())
sol = Solution()
result = sol.coinChange(coins, amount)
print(result)
Java
import java.util.*;
import java.io.*;
public class Main {
// 定义一个 Solution 类，包含解决硬币问题的函数
static class Solution {
// 函数功能：返回凑成总金额 amount 所需的最少硬币个数，若无法凑成则返回 -1
public int coinChange(int[] coins, int amount) {
// 初始化 dp 数组，大小为 amount+1，初始值为 amount+1（表示不可达）
int[] dp = new int[amount + 1];
Arrays.fill(dp, amount + 1);
dp[0] = 0; // 金额 0 不需要任何硬币
// 遍历所有金额
for (int i = 1; i <= amount; i++) {
// 遍历每个硬币面额
for (int coin : coins) {
if (i >= coin) {
dp[i] = Math.min(dp[i], dp[i - coin] + 1);
}
}
}
// 如果 dp[amount] 大于 amount，说明无法凑成该金额
return dp[amount] > amount ? -1 : dp[amount];
}
}
public static void main(String[] args) throws IOException {
// 使用 BufferedReader 读取输入
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// 读取第一行硬币数组（以空格分隔）
String[] coinStr = br.readLine().trim().split("\\s+");
int[] coins = new int[coinStr.length];
for (int i = 0; i < coinStr.length; i++) {
coins[i] = Integer.parseInt(coinStr[i]);
}
// 读取第二行金额
int amount = Integer.parseInt(br.readLine().trim());
Solution solution = new Solution();
int result = solution.coinChange(coins, amount);
System.out.println(result);
}
}