题解

题面描述

给定一个整数数组 $coins$ 表示不同面额的硬币，以及一个整数 $amount$ 表示总金额。要求计算并返回凑成总金额所需的最少的硬币个数，如果没有任何一种硬币组合能组成总金额，则返回 $-1$。可以认为每种硬币的数量是无限的。

思路

本题采用 动态规划 的方法。

• 定义数组 $dp$，其中 $dp[i]$ 表示凑成金额 $i$ 所需的最少硬币个数。
• 初始化时：
  • $dp[0] = 0$（凑成 $0$ 金额不需要任何硬币）
  • 其他 $dp[i]$ 初始化为一个较大值（例如 $amount+1$，表示不可达）
• 状态转移：
  对于每个金额 $i$，遍历所有硬币面额 $coin$，如果 $i \ge 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 \times 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);
    }
}

Leetcode 322.零钱兑换-原题链接

题目内容

给你一个整数数组 $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] <= 2^{31} - 1$
• $0 <= amount <= 10^4$