题目描述

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

记忆化搜索（自顶向下）

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

核心思路

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

代码实现

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 为例）：

初始调用 coinChange(coins, 11, new int[11])，其中 count 数组大小为 11，初始化为 0。
rem = 11，检查 count[10]（对应金额 11，但尚未计算），进入循环。
遍历硬币：
- 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，等。
对于 rem = 11，当硬币 1 时，rem = 10 返回 count[9] = 2，所以 min = 2 + 1 = 3。
最终，count[10]（对应金额 11）被设置为 3。
过程中，每个金额最多计算一次，记忆数组避免了重复递归。

复杂度分析

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

动态规划（自底向上）

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

核心思路

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

初始化：dp = [0, MAX, MAX, ..., MAX]（长度 12 ）。
处理硬币 1：
- j 从 1 到 11：dp[1] = min(MAX, dp[0] + 1) = 1，dp[2] = min(MAX, dp[1] + 1) = 2，…，dp[11] = 11。
处理硬币 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。
处理硬币 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。
最终 dp[11] = 3，返回 3。

复杂度分析

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

如何思考这道题

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

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

来源

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

笑话人生

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

题目描述

记忆化搜索（自顶向下）

核心思路

代码实现

复杂度分析

动态规划（自底向上）

核心思路

代码实现

复杂度分析

如何思考这道题

来源