零钱兑换

题目描述

给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。

你可以认为每种硬币的数量是无限的。

示例

示例 1：

输入: coins = [1, 2, 5], amount = 11
输出: 3
解释: 11 = 5 + 5 + 1

示例 2：

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

示例 3：

输入: coins = [1], amount = 0
输出: 0

示例 4：

输入: coins = [1, 5, 10], amount = 18
输出: 5
解释: 18 = 10 + 5 + 1 + 1 + 1

解题思路

这是一个经典的完全背包问题。每种硬币可以使用无限次，目标是凑出金额 amount 的最少硬币数。

状态定义：dp[j] = 凑出金额 j 所需的最少硬币数

状态转移方程：dp[j] = min(dp[j], dp[j - coin] + 1)

初始化：dp[0] = 0，其余 dp[j] = Infinity（表示无法凑出）

遍历顺序：硬币外层、金额内层，金额正序遍历（保证每种硬币可以重复使用）。

最后，若 dp[amount] 仍为 Infinity，返回 -1。

代码实现

/**
 * 零钱兑换 — 基础版（金额外层、硬币内层）
 * @param {number[]} coins - 硬币面额数组
 * @param {number} amount - 目标金额
 * @returns {number} 最少硬币数，无法凑出返回 -1
 */
function coinChange(coins, amount) {
    if (!coins.length) return -1;
    if (!amount) return 0;

    const dp = new Array(amount + 1).fill(Number.MAX_SAFE_INTEGER);
    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);
            }
        }
    }
    return dp[amount] === Number.MAX_SAFE_INTEGER ? -1 : dp[amount];
}

/**
 * 零钱兑换 — 优化版：硬币外层、金额内层（标准完全背包写法）
 * @param {number[]} coins - 硬币面额数组
 * @param {number} amount - 目标金额
 * @returns {number} 最少硬币数，无法凑出返回 -1
 */
function coinChangeOptimized(coins, amount) {
    if (!coins.length) return -1;
    if (!amount) return 0;

    coins = [...coins].sort((a, b) => a - b);

    const dp = new Array(amount + 1).fill(Infinity);
    dp[0] = 0;

    for (const coin of coins) {
        for (let j = coin; j <= amount; j++) {
            dp[j] = Math.min(dp[j], dp[j - coin] + 1);
        }
    }
    return dp[amount] === Infinity ? -1 : dp[amount];
}

复杂度分析

• 时间复杂度：O(amount × coins.length)。
• 空间复杂度：O(amount)，dp 数组大小。

coins = [1, 2, 5], amount = 11

3