动态规划求解零钱兑换的最少硬币数量（LeetCode 322）

---

题目描述

给你一个整数数组 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

记忆化搜索（自顶向下）

记忆化搜索（递归 + 记忆）使用递归来分解问题，并通过一个记忆数组存储已计算的子问题结果，避免重复计算。

核心思路

1. 基准情况：
   • 如果金额 amount 为 0，返回 0。
   • 如果金额为负，返回 -1 表示无解。
2. 记忆化：
   • 使用数组 count 存储子问题的解，其中 count[i] 表示金额 i+1 的最少硬币数（数组下标从 0 开始）。
   • 如果当前金额已经计算过，直接返回记忆的结果。
3. 递归计算：
   • 遍历每个硬币，递归计算剩余金额 rem - coin 的解。
   • 取所有有效解中的最小值加 1（当前硬币占一个数量）。
4. 存储结果：
   • 将当前金额的解存入记忆数组，并返回。

代码实现

public int coinChange(int[] coins, int amount) {
    if (amount <= 0) {
        return 0;
    }
    return coinChange(coins, amount, new int[amount]);
}

private int coinChange(int[] coins, int rem, int[] count) {
    if (rem < 0) {
        return -1;
    }
    if (rem == 0) {
        return 0;
    }
    // 检查是否已经计算过：count[rem - 1] 对应金额 rem 的解
    if (count[rem - 1] != 0) {
        return count[rem - 1];
    }
    int min = Integer.MAX_VALUE;
    for (int coin : coins) {
        // 递归计算子问题
        int res = coinChange(coins, rem - coin, count);
        // 如果子问题有解且更优，更新最小值
        if (res >= 0 && res < min) {
            min = 1 + res;
        }
    }
    // 存储当前金额的解
    count[rem - 1] = (min == Integer.MAX_VALUE) ? -1 : min;
    return count[rem - 1];
}

动态运行过程（以 coins = [1,2,5], amount = 11 为例）：

1. 初始调用 coinChange(coins, 11, new int[11])，其中 count 数组大小为 11，初始化为 0。
2. rem = 11，检查 count[10]（对应金额 11，但尚未计算），进入循环。
3. 遍历硬币：
   • coin = 1：递归计算 rem = 10。
     • rem = 10，检查 count[9]（对应金额 10，未计算），进入循环。
     • 类似地，递归计算 rem = 9, 8, ..., 0（深度优先）。
     • 当 rem = 0 时，返回 0，然后回溯计算各金额的最小值。
     • 例如，rem = 1：计算 rem = 0 返回 0，所以 min = 1，count[0] = 1。
     • rem = 2：尝试硬币 1（rem = 1 返回 1），硬币 2（rem = 0 返回 0），所以 min = min(1+1, 1+0) = 1，count[1] = 1。
     • rem = 5：尝试硬币1、2、5，最小值为 1（直接使用硬币 5），count[4] = 1。
     • rem = 10：尝试硬币1、2、5。当硬币 5 时，rem = 5 返回 1，所以 min = 1 + 1 = 2。因此 count[9] = 2（金额 10 的解）。
   • coin = 2：递归计算 rem = 9，但可能已被计算过，直接使用 count[8]。
   • coin = 5：递归计算 rem = 6，等。
4. 对于 rem = 11，当硬币 1 时，rem = 10 返回 count[9] = 2，所以 min = 2 + 1 = 3。
5. 最终，count[10]（对应金额 11）被设置为 3。
6. 过程中，每个金额最多计算一次，记忆数组避免了重复递归。

复杂度分析

• 时间复杂度：O(amount * n)，其中 n 是硬币种类数。每个金额计算一次，每次遍历所有硬币。
• 空间复杂度：O(amount)，用于记忆数组和递归调用栈。

动态规划（自底向上）

动态规划使用一个 dp 数组来存储子问题的解，从最小金额开始逐步构建到目标金额。

核心思路

1. 初始化：
   • 创建 dp 数组，dp[i] 表示金额 i 的最少硬币数。
   • 设置 dp[0] = 0，其他初始化为 Integer.MAX_VALUE（表示尚未解决）。
2. 遍历硬币：
   • 对于每个硬币，从硬币面值开始遍历到总金额。
   • 如果金额 j 减去硬币面值有解（即 dp[j - coin] != MAX_VALUE），则更新 dp[j] = min(dp[j], dp[j - coin] + 1)。
3. 返回结果：
   • 如果 dp[amount] 仍为 MAX_VALUE，返回 -1，否则返回 dp[amount]。

代码实现

public int coinChange(int[] coins, int amount) {
    // 创建 dp 数组，dp[i] 表示金额 i 所需的最少硬币数
    int[] dp = new int[amount + 1];
    // 初始化 dp 数组，除 0 外都设为最大值
    Arrays.fill(dp, Integer.MAX_VALUE);
    dp[0] = 0;
    // 遍历每种硬币
    for (int coin : coins) {
        // 对于当前硬币，从 coin 开始到 amount 更新 dp 数组
        for (int j = coin; j <= amount; j++) {
            // 如果 j-coin 有解，则更新 dp[j]
            if (dp[j - coin] != Integer.MAX_VALUE) {
                dp[j] = Math.min(dp[j], dp[j - coin] + 1);
            }
        }
    }
    // 如果 dp[amount] 无解，返回-1
    return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];
}

动态运行过程（以 coins = [1,2,5], amount = 11 为例）：

1. 初始化：dp = [0, MAX, MAX, ..., MAX]（长度 12 ）。
2. 处理硬币 1：
   • j 从 1 到 11：dp[1] = min(MAX, dp[0] + 1) = 1，dp[2] = min(MAX, dp[1] + 1) = 2，…，dp[11] = 11。
3. 处理硬币 2：
   • j 从 2 到 11：
   • j=2：dp[2] = min(2, dp[0] + 1) = 1。
   • j=3：dp[3] = min(3, dp[1] + 1) = 2。
   • j=4：dp[4] = min(4, dp[2] + 1) = 2。
   • j=5：dp[5] = min(5, dp[3] + 1) = 3。
   • … 继续更新直到 j=11。
4. 处理硬币 5：
   • j 从 5 到 11：
   • j=5：dp[5] = min(3, dp[0] + 1) = 1。
   • j=6：dp[6] = min(3, dp[1] + 1) = 2。
   • j=7：dp[7] = min(3, dp[2] + 1) = 2。
   • j=8：dp[8] = min(4, dp[3] + 1) = 3。
   • j=9：dp[9] = min(4, dp[4] + 1) = 3。
   • j=10：dp[10] = min(5, dp[5] + 1) = 2。
   • j=11：dp[11] = min(6, dp[6] + 1) = 3。
5. 最终 dp[11] = 3，返回 3。

复杂度分析

• 时间复杂度：O(amount * n)，因为外层循环遍历硬币，内层循环遍历金额。
• 空间复杂度：O(amount)，用于 dp 数组。

如何思考这道题

1. 识别问题类型：这是一个优化问题（最小硬币数），且具有重叠子问题（同一金额可能多次计算）和最优子结构（当前金额的解依赖于子问题的解），适合用动态规划解决。
2. 定义状态：通常定义 dp[i] 为金额 i 所需的最少硬币数。
3. 状态转移方程：对于每个硬币 c，如果 dp[i - c] 计算过，则 dp[i] = min(dp[i], dp[i - c] + 1)。
4. 初始化：dp[0] = 0，因为金额 0 不需要硬币；其他初始化为一个大值，表示未知。
5. 选择方法：
   • 记忆化搜索：适合递归思维，避免重复计算，但可能有递归开销。
   • 动态规划：直接迭代填充数组，通常更高效。
6. 考虑边界：金额为 0 时返回 0；硬币面值可能大于金额，需跳过。
7. 测试用例：用示例验证代码，例如 coins = [2], amount = 3 应返回 -1。

通过以上步骤，可以系统地解决此类动态规划问题。实际应用中，自底向上的动态规划往往更受欢迎，因为它避免了递归开销且代码简洁。

来源

322. 零钱兑换 | 力扣（LeetCode）
322. 零钱兑换 | 题解 | 力扣官方题解

---