对前端开发者而言，学习算法绝非为了“炫技”。它是你从“页面构建者”迈向“复杂系统设计者”的关键阶梯。它将你的编码能力从“实现功能”提升到“设计优雅、高效解决方案”的层面。从现在开始，每天投入一小段时间，结合前端场景去理解和练习，你将会感受到自身技术视野和问题解决能力的质的飞跃。------ 算法：资深前端开发者的进阶引擎

LeetCode 322. 零钱兑换：前端开发者的动态规划实战

1. 题目描述

1.1 题目内容

给定不同面额的硬币 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

2. 问题分析

这是一个典型的动态规划问题，类似于完全背包问题。核心挑战在于：

• 硬币无限供应：每种硬币可以重复使用。
• 求最小硬币数：目标是找到组合成目标金额的最少硬币数量，而不是所有可能组合。
• 无解情况：如果无法凑出金额，需返回 -1。

对于前端开发者，理解此问题有助于处理诸如资源优化、状态管理等场景，其中需要高效计算最优解。

3. 解题思路

3.1 思路概览

常见解题思路包括暴力递归、带记忆的递归（自顶向下动态规划）和自底向上动态规划。最优解是自底向上动态规划，因为它避免了递归开销，且时间和空间复杂度最优。

3.2 思路详解

• 暴力递归：直接尝试所有硬币组合，通过递归遍历所有可能路径。但会导致指数级时间复杂度，不适用于较大输入。
• 带记忆的递归（自顶向下动态规划）：在递归基础上添加备忘录（Memoization），存储已计算子问题的结果，避免重复计算。时间复杂度优化为多项式级别。
• 自底向上动态规划：使用数组迭代计算从 0 到 amount 每个金额的最少硬币数。这是最推荐的方法，因为它直观、高效，且易于理解和实现。

最优解：自底向上动态规划，时间复杂度 O(amount * n)，空间复杂度 O(amount)，其中 n 为硬币种类数。

4. 代码实现

4.1 思路一：暴力递归

/**
 * 暴力递归解法
 * @param {number[]} coins - 硬币面额数组
 * @param {number} amount - 目标金额
 * @return {number} - 最少硬币数或 -1
 */
function coinChange(coins, amount) {
    // 定义递归函数，remain 为剩余金额
    function dfs(remain) {
        // 基准情况：剩余金额小于 0，表示无解
        if (remain < 0) return -1;
        // 基准情况：剩余金额为 0，表示已凑齐，不需要更多硬币
        if (remain === 0) return 0;

        let minCoins = Infinity; // 初始化最小硬币数为无穷大
        // 遍历每种硬币
        for (let coin of coins) {
            // 递归计算使用当前硬币后的子问题
            const subResult = dfs(remain - coin);
            if (subResult !== -1) {
                // 如果子问题有解，更新最小硬币数
                minCoins = Math.min(minCoins, subResult + 1);
            }
        }
        // 如果 minCoins 仍为无穷大，表示无解，否则返回 minCoins
        return minCoins === Infinity ? -1 : minCoins;
    }

    return dfs(amount);
}

// 示例测试
console.log(coinChange([1, 2, 5], 11)); // 输出: 3
console.log(coinChange([2], 3));        // 输出: -1

步骤分解说明：

1. 从目标金额 amount 开始递归。
2. 每次递归尝试使用每个硬币，减少剩余金额。
3. 当剩余金额为 0 时，返回 0（表示成功组合）。
4. 如果所有尝试都无效，返回 -1。
5. 此方法会重复计算大量子问题，导致效率低下。

4.2 思路二：带记忆的递归（自顶向下动态规划）

/**
 * 带记忆的递归解法（自顶向下动态规划）
 * @param {number[]} coins - 硬币面额数组
 * @param {number} amount - 目标金额
 * @return {number} - 最少硬币数或 -1
 */
function coinChange(coins, amount) {
    // 备忘录数组，存储已计算金额的最少硬币数，初始为 undefined
    const memo = new Array(amount + 1).fill(undefined);

    /**
     * 递归辅助函数
     * @param {number} remain - 剩余金额
     * @return {number} - 最少硬币数或 -1
     */
    function dfs(remain) {
        // 基准情况
        if (remain < 0) return -1;
        if (remain === 0) return 0;

        // 如果已计算过，直接返回备忘录中的值
        if (memo[remain] !== undefined) return memo[remain];

        let minCoins = Infinity;
        for (let coin of coins) {
            const subResult = dfs(remain - coin);
            if (subResult !== -1) {
                minCoins = Math.min(minCoins, subResult + 1);
            }
        }

        // 存储计算结果到备忘录
        memo[remain] = minCoins === Infinity ? -1 : minCoins;
        return memo[remain];
    }

    return dfs(amount);
}

// 示例测试
console.log(coinChange([1, 2, 5], 11)); // 输出: 3
console.log(coinChange([2], 3));        // 输出: -1

关键改进：

• 使用 memo 数组缓存子问题结果，避免重复递归。
• 时间复杂度显著降低，但仍有递归调用栈的开销。

4.3 思路三：自底向上动态规划（最优解）

/**
 * 自底向上动态规划解法
 * @param {number[]} coins - 硬币面额数组
 * @param {number} amount - 目标金额
 * @return {number} - 最少硬币数或 -1
 */
function coinChange(coins, amount) {
    // dp[i] 表示组成金额 i 所需的最少硬币数，初始化为 Infinity 表示不可达
    const dp = new Array(amount + 1).fill(Infinity);
    dp[0] = 0; // 金额为 0 时不需要硬币

    // 遍历所有金额从 1 到 amount
    for (let i = 1; i <= amount; i++) {
        // 遍历每种硬币
        for (let coin of coins) {
            // 如果当前金额大于等于硬币面额，则尝试使用该硬币
            if (i - coin >= 0) {
                // 状态转移方程：dp[i] = min(dp[i], dp[i - coin] + 1)
                dp[i] = Math.min(dp[i], dp[i - coin] + 1);
            }
        }
    }

    // 如果 dp[amount] 仍为 Infinity，表示无解，否则返回其值
    return dp[amount] === Infinity ? -1 : dp[amount];
}

// 示例测试
console.log(coinChange([1, 2, 5], 11)); // 输出: 3
console.log(coinChange([2], 3));        // 输出: -1

步骤分解说明：

1. 初始化 dp 数组，dp[0] = 0 作为基础状态。
2. 对于每个金额 i，遍历所有硬币，如果硬币面额小于等于 i，则更新 dp[i] 为使用该硬币后的最小硬币数。
3. 状态转移方程：dp[i] = Math.min(dp[i], dp[i - coin] + 1)，表示从金额 i - coin 加上一枚硬币得到金额 i。
4. 最终 dp[amount] 即为结果。

5. 各实现思路的复杂度、优缺点对比表格

思路	时间复杂度	空间复杂度	优点	缺点
暴力递归	O(n^amount)	O(amount)	简单直观，易于理解	指数级时间，超时严重，不适用于实际应用
带记忆的递归（自顶向下）	O(amount * n)	O(amount)	避免重复计算，效率较高，递归思路清晰	递归栈开销，可能堆栈溢出，代码稍复杂
自底向上动态规划（最优）	O(amount * n)	O(amount)	迭代实现，无递归开销，效率最高，易于优化	需要额外数组，状态转移需仔细设计

说明：

• n 为硬币种类数（coins.length）。
• 自底向上动态规划是最优选择，尤其在前端性能敏感场景中（如大型状态计算）。

6. 总结

6.1 通用解题模板

对于这类动态规划问题，尤其是涉及最优化和无限使用元素的场景，可以遵循以下模板：

1. 定义状态：通常用 dp[i] 表示目标为 i 时的最优解（如最少硬币数）。
2. 初始化状态：设置基础情况，如 dp[0] = 0。
3. 状态转移方程：找出 dp[i] 与子问题（如 dp[i - coin]）的关系，例如 dp[i] = min(dp[i], dp[i - coin] + 1)。
4. 迭代计算：从最小子问题开始，逐步计算到目标状态。
5. 返回结果：检查是否有解，并返回最终状态值。

6.2 类似 LeetCode 题目

• LeetCode 518. 零钱兑换 II：计算凑成总金额的硬币组合数，而非最少硬币数。同样使用动态规划，但状态转移方程侧重计数。
• LeetCode 279. 完全平方数：给定正整数 n，找到最少的完全平方数（如 1, 4, 9, …）使得它们的和等于 n。可视为硬币面额为完全平方数的零钱兑换问题。
• LeetCode 377. 组合总和 Ⅳ：计算所有可能组合的个数，元素可重复使用，但顺序不同视为不同组合。
• LeetCode 416. 分割等和子集：背包问题的变种，判断数组是否能分成两个和相等的子集。