每日算法 — 使用java实现零钱兑换：完全背包动态规划与记忆化搜索

可莉爸爸 AI算法

问题引入

假设你是一名自动售货机的开发者。机器需要给顾客找零，面额有 1 元、2 元、5 元等若干种硬币。给定一个目标金额 amount，请问最少需要多少枚硬币才能凑出这个金额？如果无法凑出，返回 -1。

这个问题在 LeetCode 上编号 322，被归类为经典的完全背包问题。它与 0-1 背包的区别在于：每种硬币可以无限次使用。本文将用 Java 从零实现三种核心解法，并对比它们的时空复杂度。

问题建模

输入与输出

  • 输入：整数数组 coins 表示可用硬币面额，整数 amount 表示目标金额。
  • 输出：凑成 amount 所需的最少硬币数，若无法凑成则返回 -1。

示例

输入: coins = [1, 2, 5], amount = 11
输出: 3
解释: 11 = 5 + 5 + 1，共 3 枚硬币

输入: coins = [2], amount = 3
输出: -1
解释: 无法用面额为 2 的硬币凑出 3

状态定义

设 dp[i] 表示凑出金额 i 所需的最少硬币数。我们的目标是求 dp[amount]。

状态转移方程

对于每一个金额 i，我们遍历所有硬币面额 coin：

如果 i >= coin:
    dp[i] = min(dp[i], dp[i - coin] + 1)

初始条件：dp[0] = 0（凑出金额 0 需要 0 枚硬币），其余 dp[i] = ∞（初始表示不可达）。

解法一：记忆化搜索（自顶向下）

记忆化搜索是递归与动态规划的桥梁。它从目标金额 amount 出发，递归分解子问题，并将已计算的结果缓存起来避免重复计算。

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class CoinChangeMemo {

    private Map<Integer, Integer> memo = new HashMap<>();
    private int[] coins;

    /**
     * 主入口：计算凑成 amount 的最少硬币数
     */
    public int coinChange(int[] coins, int amount) {
        this.coins = coins;
        // base case：凑出 0 元需要 0 枚硬币
        memo.put(0, 0);
        int result = dfs(amount);
        return result == Integer.MAX_VALUE ? -1 : result;
    }

    /**
     * 深度优先搜索 + 记忆化
     * @param remain 剩余需要凑的金额
     * @return 凑成 remain 所需的最少硬币数，不可达则返回 MAX_VALUE
     */
    private int dfs(int remain) {
        // 已经计算过，直接返回缓存结果
        if (memo.containsKey(remain)) {
            return memo.get(remain);
        }

        // 尝试每一种硬币
        int minCoins = Integer.MAX_VALUE;
        for (int coin : coins) {
            if (remain >= coin) {
                int subResult = dfs(remain - coin);
                if (subResult != Integer.MAX_VALUE) {
                    minCoins = Math.min(minCoins, subResult + 1);
                }
            }
        }

        // 缓存结果
        memo.put(remain, minCoins);
        return minCoins;
    }

    public static void main(String[] args) {
        CoinChangeMemo solution = new CoinChangeMemo();
        int[] coins = {1, 2, 5};
        int amount = 11;
        System.out.println("记忆化搜索结果: " + solution.coinChange(coins, amount)); // 输出 3
    }
}

复杂度分析

  • 时间复杂度：O(amount × n)，其中 n 为硬币种类数。每个金额最多计算一次，每次计算遍历所有硬币。
  • 空间复杂度：O(amount)，递归栈深度与记忆化哈希表各占 O(amount)。

解法二：动态规划（自底向上）

自底向上的动态规划直接按照金额从小到大的顺序填充 dp 数组，避免了递归的栈开销。

public class CoinChangeDP {

    /**
     * 自底向上动态规划
     * dp[i] = 凑成金额 i 所需的最少硬币数
     */
    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 元需要 0 枚硬币

        // 遍历每一个目标金额
        for (int i = 1; i <= amount; i++) {
            // 尝试每一种硬币
            for (int coin : coins) {
                if (i >= coin) {
                    // 状态转移：使用一枚 coin 后，剩余 i - coin 的最优解 + 1
                    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) {
        CoinChangeDP solution = new CoinChangeDP();
        int[] coins = {1, 2, 5};
        int amount = 11;
        System.out.println("DP 结果: " + solution.coinChange(coins, amount)); // 输出 3
    }
}

为什么初始化为 amount + 1？

在最坏情况下（只有 1 元硬币），凑成 amount 需要 amount 枚硬币。因此任何大于 amount 的值都可以作为”无穷大”的哨兵值。

解法三：BFS 最短路径视角

换个角度思考：每一种金额可以看作图中的一个节点，使用一枚硬币面额相当于走过一条边权为 1 的边。那么问题转化为从节点 0 到节点 amount 的最短路径。

import java.util.LinkedList;
import java.util.Queue;

public class CoinChangeBFS {

    /**
     * BFS 求解最短路径
     * 每个节点代表一个金额，每条边代表使用一枚硬币
     */
    public int coinChange(int[] coins, int amount) {
        if (amount == 0) return 0;

        boolean[] visited = new boolean[amount + 1];
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(0);
        visited[0] = true;

        int steps = 0; // 已使用的硬币数（路径长度）

        while (!queue.isEmpty()) {
            int size = queue.size();
            steps++;

            // 按层遍历，当前层所有节点使用相同数量的硬币
            for (int i = 0; i < size; i++) {
                int current = queue.poll();

                for (int coin : coins) {
                    int next = current + coin;

                    if (next == amount) {
                        return steps; // 找到目标，返回当前步数
                    }

                    if (next < amount && !visited[next]) {
                        visited[next] = true;
                        queue.offer(next);
                    }
                }
            }
        }

        return -1; // 遍历完所有可达节点仍未找到目标
    }

    public static void main(String[] args) {
        CoinChangeBFS solution = new CoinChangeBFS();
        int[] coins = {1, 2, 5};
        int amount = 11;
        System.out.println("BFS 结果: " + solution.coinChange(coins, amount)); // 输出 3
    }
}

BFS 为什么有效？

BFS 天然按路径长度（硬币数）递增的顺序搜索，第一次到达目标金额时，所用的硬币数一定是最少的。这与 Dijkstra 算法在边权为 1 时的行为一致。

空间优化：滚动数组

观察动态规划的转移方程：dp[i] 只依赖于 dp[i - coin]（即当前金额减去某枚硬币面额后的值）。由于 i - coin < i，我们在填充 dp 数组时已经是从小到大遍历，天然满足依赖顺序，因此不需要额外的滚动优化，一维数组本身就是最优空间方案。

但需要注意遍历顺序：外层循环遍历金额，内层循环遍历硬币。如果反过来（先遍历硬币再遍历金额），则变成 0-1 背包的处理方式，会导致错误。这是因为完全背包问题允许硬币重复使用，必须让每种硬币在每个金额下都被考虑。

三种解法对比

解法 时间复杂度 空间复杂度 特点
记忆化搜索 O(amount × n) O(amount) 思路直观，递归有栈溢出风险
动态规划 O(amount × n) O(amount) 无递归开销，常数更优
BFS O(amount × n) O(amount) 天然求最短路径，易于理解

在实际工程中，自底向上的动态规划是首选方案，因为它避免了递归深度限制，且常数因子最小。

完整可运行项目

下面是一个整合三种解法的完整 Java 项目，包含统一的接口定义与测试用例：

import java.util.*;

/**
 * 零钱兑换问题统一接口
 */
interface CoinChangeSolver {
    int coinChange(int[] coins, int amount);
}

/**
 * 主类：运行三种解法并对比结果
 */
public class CoinChangeMain {

    public static void main(String[] args) {
        int[][] testCoins = {
            {1, 2, 5},
            {2},
            {1},
            {1, 3, 4},
            {186, 419, 83, 408}
        };
        int[] testAmounts = {11, 3, 0, 6, 6249};
        int[] expected = {3, -1, 0, 2, 20};

        CoinChangeSolver[] solvers = {
            new MemoSolver(),
            new DPSolver(),
            new BFSSolver()
        };
        String[] solverNames = {"记忆化搜索", "动态规划", "BFS"};

        for (int i = 0; i < testCoins.length; i++) {
            System.out.println("\n测试用例 " + (i + 1) + ": coins=" + Arrays.toString(testCoins[i]) 
                + ", amount=" + testAmounts[i]);
            System.out.println("期望结果: " + expected[i]);

            for (int j = 0; j < solvers.length; j++) {
                long start = System.nanoTime();
                int result = solvers[j].coinChange(testCoins[i], testAmounts[i]);
                long end = System.nanoTime();
                System.out.printf("  %s: %d (耗时 %.3f ms)%n", 
                    solverNames[j], result, (end - start) / 1_000_000.0);
            }
        }
    }
}

/**
 * 记忆化搜索实现
 */
class MemoSolver implements CoinChangeSolver {
    private Map<Integer, Integer> memo;
    private int[] coins;

    @Override
    public int coinChange(int[] coins, int amount) {
        this.coins = coins;
        this.memo = new HashMap<>();
        memo.put(0, 0);
        int res = dfs(amount);
        return res == Integer.MAX_VALUE ? -1 : res;
    }

    private int dfs(int remain) {
        if (memo.containsKey(remain)) return memo.get(remain);
        int min = Integer.MAX_VALUE;
        for (int coin : coins) {
            if (remain >= coin) {
                int sub = dfs(remain - coin);
                if (sub != Integer.MAX_VALUE) {
                    min = Math.min(min, sub + 1);
                }
            }
        }
        memo.put(remain, min);
        return min;
    }
}

/**
 * 动态规划实现
 */
class DPSolver implements CoinChangeSolver {
    @Override
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, amount + 1);
        dp[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);
                }
            }
        }
        return dp[amount] > amount ? -1 : dp[amount];
    }
}

/**
 * BFS 实现
 */
class BFSSolver implements CoinChangeSolver {
    @Override
    public int coinChange(int[] coins, int amount) {
        if (amount == 0) return 0;
        boolean[] visited = new boolean[amount + 1];
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(0);
        visited[0] = true;
        int steps = 0;

        while (!queue.isEmpty()) {
            int size = queue.size();
            steps++;
            for (int i = 0; i < size; i++) {
                int cur = queue.poll();
                for (int coin : coins) {
                    int next = cur + coin;
                    if (next == amount) return steps;
                    if (next < amount && !visited[next]) {
                        visited[next] = true;
                        queue.offer(next);
                    }
                }
            }
        }
        return -1;
    }
}

总结

零钱兑换问题将完全背包的核心思想展现得淋漓尽致。通过本文的三种实现，你可以对比理解：

  • 记忆化搜索适合递归思路清晰、状态空间稀疏的场景；
  • 动态规划是工程中最稳定高效的选择；
  • BFS则揭示了问题与图论最短路径之间的深层联系。

掌握这一问题的建模与实现，是理解更复杂动态规划问题（如完全背包的扩展、多重背包、分组背包）的重要基石。

Tagged with: