深入理解零钱兑换问题：如何用最少的硬币凑出目标金额

引言

在现代软件开发和算法设计中，我们经常遇到一类看似简单却蕴含深意的问题：给定一组资源（如硬币），如何组合它们以达成特定目标，并且使资源的消耗量最少？这就是我们今天要深入探讨的“最小硬币数量”问题。

这不仅仅是一个数学智力题，它是理解动态规划这一核心算法思想的绝佳入口。无论你是为了准备技术面试，还是为了优化实际项目中的资源分配算法，掌握这一策略都将大有裨益。在这篇文章中，我们将摒弃枯燥的理论推导，通过直观的例子和实际代码，像实战中的开发者一样，一步步拆解这个问题，从最初的直观想法（贪心算法）的缺陷，到最终构建出稳健的动态规划解决方案。

问题描述

首先，让我们明确一下我们要解决的具体场景。假设你是一位收银员，面对一堆不同面额的硬币，你需要找给顾客特定金额的钱。你的目标很简单：给顾客的硬币数量越少越好，这样既方便顾客携带，也能简化你的工作。

具体来说，我们需要处理以下约束条件：

• 硬币面额：你拥有无限数量的不同面额硬币，存储在一个数组 INLINECODEabc9e253 中（例如 INLINECODE5c6741a5）。注意，这里每种面额的供应是无限的，这被称为“完全背包”问题的特征。
• 目标金额：你需要凑出的总金额记为 sum。
• 输出：计算出凑出 sum 所需的最少硬币数量。
• 异常处理：如果给定的硬币面额根本无法凑出该金额（例如硬币是 INLINECODE4977d63b，但要凑 INLINECODE642b84d0），则返回 -1。

示例分析

为了更直观地理解，让我们来看两个具体的例子。通过对比这两个例子，你会发现为什么这个问题并不像看起来那么简单。

示例 1：

输入：INLINECODE261abedf, INLINECODE0062187f

输出：2

解释：面对 30 的金额，最直观的选择是拿一枚 25 面额的硬币，剩下的 5 刚好可以用一枚 5 面额的硬币补齐。25 + 5 = 30，总共只需要 2 枚。这是一个非常理想的情况。
示例 2（陷阱出现）：

输入：INLINECODEfd19fd2b, INLINECODE31b1c02c

输出：2

解释：在这里，如果你每次都贪心地选择最大面额 9，剩下的金额是 2。由于没有面额为 2 的硬币，你不得不回头使用更小的硬币，导致最终方案变得复杂且非最优。而真正的最优解是选择一枚 6 和一枚 5（6 + 5 = 11），仅需 2 枚硬币。这个例子直接击碎了“只选最大面额”的贪心幻想。

思维误区：为什么贪心算法会失效？

在深入动态规划之前，我们很有必要先探讨一下为什么更简单的“贪心算法”在这里行不通。这不仅是为了避坑，更是为了理解动态规划存在的价值。

贪心算法的逻辑是：为了使硬币数量最少，我每次都优先选择面额最大的硬币。

让我们看看这种策略在上述示例 2中的表现：

• 目标是 11。最大的硬币是 9。
• 拿走 9，剩下 11 – 9 = 2。
• 现在要凑 2。最大的硬币是 1（因为 5, 6, 9 都比 2 大）。
• 只能拿两个 1。
• 最终结果：9 + 1 + 1 = 11，总共 3 枚硬币。

对比结果：贪心算法给出了 3 枚，而最优解是 2 枚（6 + 5）。
结论：贪心算法只关注眼前的“最大利益”，而忽略了后续组合的可能性。在货币系统特殊（如像美元那样 1, 5, 10, 25）时贪心可能有效，但在一般的硬币面额下，它是不可靠的。因此，我们需要一种能够“全局统筹”的算法——动态规划。

解决方案：动态规划

动态规划的核心在于将复杂的大问题分解为简单的小问题，并将小问题的解存储起来（记忆化），避免重复计算。对于这个问题，我们采用自底向上的构建方式。

核心状态定义

我们需要定义一个状态来表示子问题的解。

• 定义：创建一个一维数组 INLINECODE3379aace，其中 INLINECODEe0ad2b53 代表凑出金额 i 所需的最小硬币数量。
• 目标：我们最终需要的答案就是 dp[sum]。
• 初始状态：凑出金额 0 需要 0 个硬币，所以 dp[0] = 0。

状态转移方程

这是解决问题的关键。想象一下，如果你想凑出金额 INLINECODEdcee6608（比如 11），而你手头有一枚面额为 INLINECODEf19043c1（比如 5）的硬币，那么凑出 i 的方案就可以转化为：

凑出 i 的数量 = 1 (这枚硬币) + 凑出 (i - coin) 的数量

即：dp[i] = 1 + dp[i - coin]。

但是，我们手头有 INLINECODEb56f81d3 数组中的多种硬币。为了找到最小值，我们需要尝试用每一种硬币去凑金额 INLINECODEeb5362c6，然后从中取最小值。

完整的转移方程：

dp[i] = min(dp[i], 1 + dp[i - coins[j]]) 

对于每一个 INLINECODEb22f7963 从 1 遍历到 INLINECODEe51bbfc8，我们都要尝试所有硬币 j。

算法步骤详解

• 初始化：创建大小为 INLINECODE404c93b0 的数组 INLINECODEbd42094c。
• 设定基准：dp[0] = 0。
• 填充无穷大：将 INLINECODEac6f0378 到 INLINECODE9b853d7a 的初始值设为一个很大的数（例如 INLINECODE23576a56 或 INLINECODE7ea6fad4），表示“尚未找到解”或“不可达”。这在逻辑上充当了正无穷大的角色，方便后续取 min 操作。
• 双重循环：

* 外层循环：遍历金额 INLINECODEf18ab2c1 从 1 到 INLINECODEdb467256。

* 内层循环：遍历硬币数组 coins[]。

• 条件更新：对于每一对 INLINECODE6d9af58e，如果 INLINECODEf9cac446（意味着硬币面额不能比当前要凑的目标金额大），我们检查 INLINECODE77286d2c 是否可达（不是无穷大）。如果是，则更新 INLINECODE45063881。
• 结果判定：最后检查 INLINECODE1e17a4eb。如果它依然是那个初始的“无穷大”值，说明无法凑出，返回 -1；否则返回 INLINECODE5d572942。

代码实现与解析

为了让你能够在实际开发中直接应用，我们提供了多种主流语言的实现。请注意阅读代码中的注释，它们详细解释了每一行的作用。

1. Python 实现

Python 的实现非常简洁，适合快速原型开发。这里我们使用了一个非常大的浮点数来代表“无穷大”。

def minCoins(coins, sum):
    # dp[i] 将存储凑出金额 i 所需的最小硬币数
    # 初始化数组，长度为 sum + 1
    dp = [float(‘inf‘)] * (sum + 1)
    
    # 基本情况：凑出金额 0 不需要任何硬币
    dp[0] = 0
    
    # 遍历从 1 到 sum 的每一个目标金额
    for i in range(1, sum + 1):
        # 尝试每一种硬币
        for coin in coins:
            # 只有当硬币面额小于等于当前目标金额 i 时，才考虑使用它
            if coin <= i:
                # 状态转移：dp[i] 可以是 当前值 或 (1 + dp[i-coin]) 中的较小值
                dp[i] = min(dp[i], 1 + dp[i - coin])
    
    # 如果 dp[sum] 仍是无穷大，说明无法凑出，返回 -1
    return -1 if dp[sum] == float('inf') else dp[sum]

2. Java 实现

在 Java 中，我们需要注意整数的溢出问题。INLINECODEa2feab29 用于初始化，在计算 INLINECODE3a0604cc 时需要特别小心，因此我们增加了一个判断条件。

public class CoinChange {
    public int minCoins(int[] coins, int sum) {
        // dp[i] 存储凑出金额 i 的最小硬币数
        int[] dp = new int[sum + 1];
        
        // 基本情况
        dp[0] = 0;
        
        // 初始化所有数值为最大值 (代表不可达)
        for (int i = 1; i <= sum; i++) {
            dp[i] = Integer.MAX_VALUE;
        }
        
        // 计算所有从 1 到 sum 的金额
        for (int i = 1; i <= sum; i++) {
            // 遍历所有硬币面额
            for (int coin : coins) {
                // 硬币面额必须 <= 当前金额 i
                if (coin <= i) {
                    // 获取子问题的结果 dp[i - coin]
                    int subRes = dp[i - coin];
                    
                    // 防止溢出：只有当子问题不是 MAX_VALUE 时才进行计算
                    // 如果 subRes 是 MAX_VALUE，加 1 会变成负数，导致错误
                    if (subRes != Integer.MAX_VALUE && subRes + 1 < dp[i]) {
                        dp[i] = subRes + 1;
                    }
                }
            }
        }
        
        // 如果结果是 MAX_VALUE，返回 -1，否则返回结果
        return dp[sum] == Integer.MAX_VALUE ? -1 : dp[sum];
    }
}

3. C++ 实现

C++ 的实现逻辑与 Java 类似，但更接近底层。这里我们使用了 INT_MAX。

#include 
#include 
#include 

using namespace std;

int minCoins(vector& coins, int sum) {
    // dp[i] 存储凑出金额 i 所需的最小硬币数量
    vector dp(sum + 1);
    
    // Base case
    dp[0] = 0;
    
    // 初始化为 INT_MAX (代表无穷大)
    for (int i = 1; i <= sum; i++)
        dp[i] = INT_MAX;
    
    // 计算从 1 到 sum 的所有金额
    for (int i = 1; i <= sum; i++) {
        // 遍历所有硬币
        for (int coin : coins) {
            // 检查硬币面额是否有效
            if (coin <= i) {
                int sub_res = dp[i - coin];
                // 检查子问题是否可达，并更新最小值
                if (sub_res != INT_MAX && sub_res + 1 < dp[i])
                    dp[i] = sub_res + 1;
            }
        }
    }
    
    // 返回结果，如果不可达则返回 -1
    return dp[sum] == INT_MAX ? -1 : dp[sum];
}

4. JavaScript 实现

对于前端开发者或 Node.js 环境，这个版本可以直接运行。

function minCoins(coins, sum) {
    // 创建长度为 sum + 1 的数组，全部填充最大值
    // 这里用 Number.MAX_SAFE_INTEGER 或者一个足够大的数
    const dp = new Array(sum + 1).fill(Number.MAX_VALUE);

    // Base case
    dp[0] = 0;

    // 外层循环遍历金额
    for (let i = 1; i <= sum; i++) {
        // 内层循环遍历硬币
        for (let coin of coins) {
            if (coin <= i) {
                let subRes = dp[i - coin];
                // 确保子问题有解，并且比较大小
                if (subRes !== Number.MAX_VALUE && subRes + 1 < dp[i]) {
                    dp[i] = subRes + 1;
                }
            }
        }
    }

    return dp[sum] === Number.MAX_VALUE ? -1 : dp[sum];
}

5. C# 实现

最后是 C# 版本，适用于 .NET 开发者。

public int MinCoins(int[] coins, int sum) {
    // dp[i] 将存储数值 i 所需的最小硬币数量
    int[] dp = new int[sum + 1];

    // Base case
    dp[0] = 0;

    // 初始化所有数值为最大值
    for (int i = 1; i <= sum; i++) {
        dp[i] = int.MaxValue;
    }

    for (int i = 1; i <= sum; i++) {
        // 遍历所有硬币
        for (int j = 0; j < coins.Length; j++) {
            if (coins[j] <= i) {
                int subRes = dp[i - coins[j]];
                // 只有当子结果不是 MaxValue 时才更新，防止溢出
                if (subRes != int.MaxValue && subRes + 1 < dp[i]) {
                    dp[i] = subRes + 1;
                }
            }
        }
    }

    return dp[sum] == int.MaxValue ? -1 : dp[sum];
}

复杂度分析

在选择算法时，理解其效率至关重要。让我们对上述解法进行剖析。

时间复杂度：O(sum n)

这里 INLINECODE8c2bfe8a 是目标金额，INLINECODE6ff9f147 是硬币数组的长度。我们有一个嵌套循环：外层循环遍历金额 INLINECODE50bed68a 次，内层循环遍历硬币 INLINECODEe5f8f03e 次。因此，总的计算次数大致是两者的乘积。这在大多数情况下是可以接受的，尤其是当 INLINECODEf3ce4df5 不是特别大时（例如 INLINECODEaf3792cd）。

• 空间复杂度：O(sum)

我们使用了一个大小为 sum + 1 的一维数组来存储中间状态。相比递归解法可能带来的堆栈溢出风险，这种迭代的动态规划方法在空间上是线性且非常高效的。

实际应用场景与最佳实践

理解算法只是第一步，知道在哪里使用它才是高手之道。

• 货币兑换系统：这是最直接的应用。无论是银行系统、自动售货机还是在线支付平台，都需要计算最优的找零组合以减少现金流通的压力。
• 资源优化分配：想象一下你有一个容量为 INLINECODE97e24e61 的背包，你需要用不同规格的小箱子（INLINECODE1f005d0f）去填满它，且要求使用的箱子数量最少。这在物流装箱、内存块分配中都有类似的逻辑。
• 缓存策略：在设计 LRU（最近最少使用）或其他缓存变体时，有时需要计算最少操作步数来达到某种状态。

最佳实践提示：

• 预处理硬币：虽然代码逻辑上不需要硬币排序，但如果硬币数组非常巨大，先进行排序有时有助于提前终止内层循环（虽然对于这个问题，我们必须遍历所有硬币以确保找到全局最优）。
• 输入验证：在实际生产代码中，务必检查 INLINECODE269bb9bc 是否为负数，或者 INLINECODEa2496f81 数组是否为空，这些边界条件往往是系统崩溃的元凶。

总结

在这篇文章中，我们深入探讨了“最小硬币数量”问题。我们从贪心算法的局限性入手，理解了为什么简单的直觉在算法设计中往往是靠不住的。随后，我们引入了动态规划这一强大的工具，详细讲解了如何定义 dp 状态、如何构建状态转移方程，并提供了多语言的具体实现代码。

核心要点在于：将大问题分解为结构相同的小问题，并记录小问题的解以避免重复劳动。 这种思维方式不仅适用于找零问题，更是解决计算机科学中无数优化问题的金钥匙。

希望这篇文章能帮助你不仅“学会”这道题，更能“懂得”背后的算法逻辑。接下来，建议你尝试自己修改代码，例如添加打印具体硬币组合的功能，或者尝试解决当硬币数量有限（0/1 背包问题）时的情况，以进一步巩固你的理解。