硬币找零问题详解及动态规划解法

硬币找零问题是一个经典的算法问题，考察如何用最少的硬币凑出指定金额。很多面试和实际开发中都会碰到类似问题。下面将详细讲解硬币找零问题，并通过 动态规划 的方式解决它。

问题描述：

假设有不同面值的硬币，例如 {1, 2, 5}，希望用这些硬币凑出一个总金额 n。你的目标是使用最少数量的硬币。

例子：

• 硬币面值：1, 2, 5
• 目标金额：11
• 可以选择 2 枚 5 元硬币，再加 1 枚 1 元硬币，最终共 3 枚硬币就可以凑出 15 元。

目标是写一个程序，能自动计算出给定硬币面值和目标金额的最优解。

---

解题思路

这个问题看似简单，但如果不使用正确的算法，很容易陷入枚举所有可能组合的困境，导致计算复杂度爆炸。比如，如果硬币面值非常多，或者目标金额非常大，用暴力穷举的方式会导致效率非常低。因此，可以使用 动态规划 来解决这个问题。

什么是动态规划？

动态规划是一种算法思想，旨在通过将问题分解为子问题，逐步构建最终答案。动态规划会保存已经解决的子问题结果，从而避免重复计算。

在硬币找零问题中，可以将问题分解为“如何用最少的硬币凑出 0 元、1 元、2 元…直到 n 元。”。

动态规划解法

1. 定义状态

用一个数组 dp[]，其中 dp[i] 表示凑出金额 i 所需要的最少硬币数。

2. 状态转移方程

对于每一个金额 i，如果已经知道了用最少的硬币凑出金额 i - coin 的最优解（其中 coin 是硬币面值之一），那么凑出 i 的最少硬币数就是 dp[i - coin] + 1。

因此，状态转移方程是：

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

这个公式的含义是，对于每一个金额 i，我们尝试用每一种硬币 coin 去更新 dp[i]。选择一种能让 dp[i] 最小的组合。

3. 初始化

初始化 dp[0] = 0，表示凑出金额 0 需要 0 枚硬币。其他金额的 dp[i] 初始值设为无穷大（用 Integer.MAX_VALUE 表示），表示暂时还无法凑出这个金额。

4. 最终结果

需要的答案是 dp[n]，即凑出目标金额 n 所需的最少硬币数。

代码实现

import java.util.Arrays;
public class CoinChange {
    // 动态规划求最少硬币数
    public int getMinCoinCount(int total, int[] values) {
        // dp[i] 表示金额为 i 时所需的最小硬币数
        int[] dp = new int[total + 1];
        // 初始化 dp 数组，除 dp[0] 外其他全部初始化为最大值（表示无法凑出）
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0; // 凑出金额 0 所需的硬币数是 0

        // 遍历每一种硬币面值
        for (int value : values) {
            // 更新 dp 数组，遍历从硬币面值到目标金额 total
            for (int i = value; i <= total; i++) {
                if (dp[i - value] != Integer.MAX_VALUE) {
                    dp[i] = Math.min(dp[i], dp[i - value] + 1);
                }
            }
        }
        // 如果 dp[total] 仍然为最大值，说明无法凑出 total，返回 -1
        return dp[total] == Integer.MAX_VALUE ? -1 : dp[total];
    }

    public static void main(String[] args) {
        CoinChange coinChange = new CoinChange();
        int[] values = {5, 2, 1}; // 硬币面值
        int total = 11; // 总价
        int minCoin = coinChange.getMinCoinCount(total, values);
        System.out.println("最少硬币数量: " + minCoin);
    }
}

代码解释

1. 初始化 dp[] 数组：

   • dp[i] 表示凑出金额 i 所需的最少硬币数。我们先将所有金额的值设为无穷大，表示暂时无法凑出该金额。
   • dp[0] = 0，因为凑出 0 元不需要任何硬币。

2. 遍历硬币面值：

   • 对于每一个硬币面值 value，从该面值开始遍历金额，并更新 dp[] 数组。
   • 如果 dp[i - value] 是一个有效的值（即不是无穷大），那么就可以通过使用一个 value 面值的硬币来凑出金额 i，更新 dp[i] 为 dp[i - value] + 1。

3. 结果输出：

   • 如果 dp[total] 还是无穷大，说明无法用给定的硬币凑出目标金额，输出 -1。否则输出 dp[total]，表示最少的硬币数量。

动态规划过程

为了更清晰地理解动态规划的执行过程，可以参考下面这张图，它展示了如何使用面值为 1, 2, 5 的硬币，凑出从 0 到 11 的最优解：

表格：

F(i)	1 (面值1硬币)	5 (面值5硬币)	2 (面值2硬币)	最优解
F(0)	0	不选	不选	0
F(1)	1 + F(0) = 1	不选	不选	1
F(2)	1 + F(1) = 2	不选	1 + F(0) = 1	1
F(3)	1 + F(2) = 2	不选	1 + F(1) = 2	2
F(4)	1 + F(3) = 3	不选	1 + F(2) = 2	2
F(5)	1 + F(4) = 3	1 + F(0) = 1	1 + F(3) = 3	1
F(6)	1 + F(5) = 2	1 + F(1) = 2	1 + F(4) = 3	2
F(7)	1 + F(6) = 3	1 + F(2) = 2	1 + F(5) = 2	2
F(8)	1 + F(7) = 3	1 + F(3) = 3	1 + F(6) = 2	3
F(9)	1 + F(8) = 4	1 + F(4) = 3	1 + F(7) = 3	3
F(10)	1 + F(9) = 5	1 + F(5) = 2	1 + F(8) = 3	2
F(11)	1 + F(10) = 3	1 + F(6) = 3	1 + F(9) = 4	3

解释：

在表格中，每一行表示凑出某个金额 F(i) 的最优解。在每一列中，可以看到不同硬币面值的选择及其影响。最终可以看到凑出 F(15) 时，最少需要 3 枚硬币。

运行结果

对于硬币面值 {1, 5, 11} 和目标金额 15，程序输出：

凑出金额 15 需要的最少硬币数: 3

算法复杂度

• 时间复杂度：O(n * m)，其中 n 是目标金额，m 是硬币面值的数量。需要对每个硬币面值遍历所有金额。
• 空间复杂度：O(n)，需要一个长度为 total + 1 的数组来存储每个金额的最优解。

总结

动态规划提供了一种高效解决硬币找零问题的方式。通过保存已经计算出的结果，避免了大量重复计算，从而大大提高了算法的效率。这个思路不仅适用于硬币找零问题，还可以扩展到很多类似的最优化问题中。