硬币找零问题

给你一个整数数组 coins，表示不同面额的硬币；以及一个整数 amount，表示总金额。

计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1。

你可以认为每种硬币的数量是无限的。

示例

示例 1:

输入: coins = [1, 2, 5], amount = 11

输出: 3

解释: 11 = 5 + 5 + 1

示例 2:

输入: coins = [2], amount = 3

输出: -1

示例 3:

输入: coins = [1], amount = 0

输出: 0

提示:

• 1 <= coins.length <= 12
• 1 <= coins[i] <= 2^31 - 1
• 0 <= amount <= 10^4

解题思路

该问题可建模为以下优化问题:

[ \min \sum_{i=0}^{n} x_i ] [ \text{subject to} \sum_{i=0}^{n} x_i \cdot c_i = S ]

其中, S 是总金额, c_i 是第 i 枚硬币的面值, x_i 是面值为 c_i 的硬币数量。

一个简单的解决方案是通过回溯的方法枚举每个硬币数量子集 [x_0, ..., x_{n-1}], 针对给定的子集计算它们组成的金额数, 如果金额数为 S, 则记录返回合法硬币总数的最小值, 反之返回 -1。该做法的时间复杂度为 O(S^n), 会超出时间限制, 因此必须加以优化。

运用动态规划

我们采用自下而上的方式进行思考。仍定义 F(i) 为组成金额 i 所需最少的硬币数量, 假设在计算 F(i) 之前, 我们已经计算出 F(0) 到 F(i-1) 的答案。则 F(i) 对应的转移方程应为:

[ F(i) = \min_{j=0 \ldots n-1} F(i - c_j) + 1 ]

其中 c_j 代表的是第 j 枚硬币的面值。

代码实现

C++

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        int Max = amount + 1;
        vector<int> dp(amount + 1, Max);
        dp[0] = 0;
        for (int i = 1; i <= amount; ++i) {
            for (int j = 0; j < (int)coins.size(); ++j) {
                if (coins[j] <= i) {
                    dp[i] = min(dp[i], dp[i - coins[j]] + 1);
                }
            }
        }
        return dp[amount] > amount ? -1 : dp[amount];
    }
};
```python
class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        dp = [float('inf')] * (amount + 1)
        dp[0] = 0
        
        for coin in coins:
            for x in range(coin, amount + 1):
                dp[x] = min(dp[x], dp[x - coin] + 1)
        
        return dp[amount] if dp[amount] != float('inf') else -1
复杂度分析
时间复杂度: O(Sn)，其中 S 是金额，n 是面额数。
空间复杂度: O(S)。