0322.零钱兑换

难度：🟡 中等

标签：广度优先搜索、数组、动态规划

链接：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

解题思路

核心思想

本题是经典的动态规划问题，属于“完全背包”问题的一种变体。其核心思想是，要求解凑成总金额 amount 所需的最少硬币数，我们可以将其分解为子问题：凑成金额 i 所需的最少硬币数。

思路选择

动态规划 (Dynamic Programming) 是解决此问题的标准最优思路。

• 我们可以定义一个 dp 数组，其中 dp[i] 表示凑成金额 i 所需的最少硬币数量。我们的目标就是求 dp[amount]。

• 状态转移方程 的推导如下：对于金额 i，我们可以尝试使用 coins 数组中的每一种硬币 coin。如果我们决定使用一枚 coin，那么问题就变成了“凑成金额 i - coin 所需的最少硬币数”再加 1。我们需要在所有可能的硬币选择中，找出那个最小值。

• 因此，状态转移方程为： dp[i] = min(dp[i], dp[i - coin] + 1)，其中 coin 是 coins 数组中的一个可用硬币。

关键步骤

1. 初始化：创建一个长度为 amount + 1 的 dp 数组。dp[0] 初始化为 0（凑成金额0需要0个硬币）。将数组其余所有位置初始化为一个极大值（如 Infinity），表示初始状态下这些金额是无法凑成的。

2. 双层循环： a. 外层循环遍历所有金额 i 从 1 到 amount。 b. 内层循环遍历 coins 数组中的每一种硬币 coin。

3. 状态转移：在循环内部，如果当前金额 i 大于等于硬币面额 coin，则说明可以使用这枚硬币。此时，我们更新 dp[i] 的值：dp[i] = Math.min(dp[i], dp[i - coin] + 1)。

4. 返回结果：遍历结束后，如果 dp[amount] 的值仍然是我们初始化的极大值，说明无法凑成总金额，返回 -1。否则，返回 dp[amount]。

代码实现

/**
 * @param {number[]} coins
 * @param {number} amount
 * @return {number}
 */
var coinChange = function (coins, amount) {
    // dp[i] 表示凑成金额 i 所需的最少硬币数
    let dp = new Array(amount + 1).fill(Infinity);
    // 基线条件
    dp[0] = 0;

    // 遍历所有金额
    for (let i = 1; i <= amount; i++) {
        // 遍历所有硬币面额
        for (const coin of coins) {
            if (i >= coin) {
                // 状态转移
                dp[i] = Math.min(dp[i], dp[i - coin] + 1);
            }
        }
    }

    // 如果 dp[amount] 仍为初始值，说明无法凑成
    return dp[amount] === Infinity ? -1 : dp[amount];
};

复杂度分析

• 时间复杂度：O(S × n) 其中 S 是总金额 amount，n 是 coins 数组的长度。我们需要填充 dp 数组，对于每个金额，都需要遍历一次所有硬币。

• 空间复杂度：O(S) 我们需要一个长度为 S+1 的 dp 数组来存储中间状态。

相关题目

• 0518.零钱兑换 II

• 0070.爬楼梯

• 0279.完全平方数

总结

本题是动态规划中“凑零钱”问题的经典模型。其核心在于理解状态 dp[i] 的定义，并根据“最优子结构”的性质推导出状态转移方程。这个模型可以推广到许多类似的组合求最优解的问题中。