使用哈希表记忆化求解最少硬币数算法超时，如何优化？

现有算法的核心缺陷 #

• 回溯属于深度优先搜索逻辑，大金额下搜索路径呈指数级增长，现有记忆化剪枝规则太弱，仅当当前路径硬币数比已存储值大时才剪枝，大量无效路径没有被提前拦截。
• 每次递归都执行Object.assign([], _chosen)复制数组，递归深度较高时内存和时间开销极大，且完全不需要在递归过程中存储完整的硬币组合数组，额外占用了大量不必要的资源。
• 硬币没有排序，无法优先用大面值硬币快速得到较优的全局最小硬币数作为剪枝阈值，导致剪枝逻辑迟迟无法生效。
• 缺少上限剪枝规则：当前已经使用k个硬币凑出a金额，剩余待凑金额为目标金额 - a，哪怕全用最大面值硬币计算出的最少需要硬币数加上k已经大于等于当前已知的最小硬币数时，没有提前终止该路径的搜索。
• 记忆化逻辑触发时机靠后，很多重复金额的递归逻辑还是会被执行，没有提前拦截无效路径。

优化修改方案 #

1. 前置预处理优化 #

先对硬币数组按从大到小降序排序，优先尝试大面值硬币，快速得到一个较优的初始最小硬币数作为剪枝阈值，让后续剪枝逻辑可以更早生效。

2. 砍掉冗余存储 #

不需要存储完整的硬币组合数组，coinAmounts仅存储每个金额对应的最少硬币数即可，如果需要输出具体组合，可以最后通过反向推导dp结果生成，不需要在递归过程中维护，直接砍掉90%以上的内存和拷贝开销。

3. 强化剪枝逻辑 #

• 全局维护当前找到的最少硬币数minCount，初始值设为无穷大，只要当前递归路径的硬币数已经大于等于minCount，直接返回不需要继续搜索。
• 每次递归入口先判断当前金额的已存最少硬币数是否小于等于当前路径的硬币数，如果是直接返回，不需要继续执行。
• 增加边界剪枝：如果当前金额加上当前硬币面值已经超过目标金额，直接跳过该硬币。

4. 可选：改用稳定的迭代式动态规划 #

如果要彻底解决大输入超时问题，建议直接使用标准自底向上动态规划实现，时间复杂度稳定为O(amount * 硬币数量)，对于目标金额8839的场景完全无压力，示例代码如下：

var coinChange = function(coins, amount) {
    const dp = new Array(amount + 1).fill(Infinity);
    dp[0] = 0;
    for (let i = 1; i <= amount; i++) {
        for (const coin of coins) {
            if (coin <= i) {
                dp[i] = Math.min(dp[i], dp[i - coin] + 1);
            }
        }
    }
    return dp[amount] === Infinity ? -1 : dp[amount];
};

如果一定要保留回溯+记忆化的写法，优化后的核心代码示例：

var coinChange = function(coins, amount) {
    if (amount === 0) return 0;
    // 降序排序优先尝试大面值，快速得到初始剪枝阈值
    coins.sort((a, b) => b - a);
    let minCount = Infinity;
    // 仅存储每个金额对应的最少硬币数，不需要存完整组合
    const memo = new Map();

    const backtrack = (currentSum, count) => {
        // 超过目标金额直接返回
        if (currentSum > amount) return;
        // 当前硬币数已经超过已知最小值，无需继续搜索
        if (count >= minCount) return;
        // 该金额已经有更优解法，直接返回
        if (memo.has(currentSum) && memo.get(currentSum) <= count) return;
        // 更新记忆表
        memo.set(currentSum, count);
        // 命中目标，更新全局最小值
        if (currentSum === amount) {
            minCount = Math.min(minCount, count);
            return;
        }
        // 遍历硬币递归
        for (const coin of coins) {
            backtrack(currentSum + coin, count + 1);
        }
    };

    backtrack(0, 0);
    return minCount === Infinity ? -1 : minCount;
};

内容的提问来源于stack exchange，提问作者Ravi L