硬币找零问题详解（Java实现动态规划解决找零钱算法）

什么是硬币找零问题？

给定一个目标金额 amount 和一组硬币面值（例如 [1, 5, 10, 25]），要求找出组成该金额所需的最少硬币数量。如果无法组成，则返回 -1。

例如：

• 目标金额：11 元
• 硬币面值：[1, 2, 5]
• 最优解：5 + 5 + 1 = 11，共需 3 枚硬币

为什么用动态规划？

暴力递归虽然可行，但效率极低（指数级时间复杂度）。而动态规划找零钱方法可以将问题分解为子问题，避免重复计算，大大提升效率。

核心思想：

要凑出金额 n，我们可以尝试每一种硬币 coin，然后看能否用更少的硬币凑出 (n - coin)。

Java 实现代码

下面是一个完整的 Java 程序，使用动态规划解决硬币找零问题：

public class CoinChange {    public static int coinChange(int[] coins, int amount) {        // 创建 dp 数组，dp[i] 表示凑出金额 i 所需的最少硬币数        int[] dp = new int[amount + 1];                // 初始化 dp 数组为 amount + 1（一个不可能达到的大值）        for (int i = 0; i <= amount; i++) {            dp[i] = amount + 1;        }                // 凑出金额 0 需要 0 枚硬币        dp[0] = 0;                // 遍历所有金额        for (int i = 1; i <= amount; i++) {            // 尝试每一种硬币            for (int coin : coins) {                if (coin <= i) {                    // 状态转移方程                    dp[i] = Math.min(dp[i], dp[i - coin] + 1);                }            }        }                // 如果 dp[amount] 仍为初始大值，说明无法凑出        return dp[amount] > amount ? -1 : dp[amount];    }    public static void main(String[] args) {        int[] coins = {1, 2, 5};        int amount = 11;                int result = coinChange(coins, amount);        System.out.println("最少需要硬币数量: " + result); // 输出: 3    }}

代码解析

1. dp 数组初始化：我们创建一个长度为 amount + 1 的数组，初始值设为 amount + 1（比任何可能解都大）。
2. 边界条件：金额为 0 时，不需要任何硬币，所以 dp[0] = 0。
3. 状态转移：对每个金额 i，遍历所有硬币。如果硬币面值 ≤ i，则尝试用这枚硬币，并更新 dp[i]。
4. 结果判断：若最终 dp[amount] 仍大于 amount，说明无法凑出，返回 -1。

时间与空间复杂度

• 时间复杂度：O(amount × coins.length)
• 空间复杂度：O(amount)

总结

通过本教程，你已经学会了如何用 Java硬币找零 算法解决实际问题。掌握动态规划找零钱技巧，不仅能应对面试题，还能提升你的算法思维能力。

记住：编程不是死记硬背，而是理解逻辑。多练习类似问题（如背包问题、最长公共子序列等），你会越来越熟练！

希望这篇Java编程教程对你有帮助。如果你有任何疑问，欢迎在评论区留言！