Coin Change问题两段相似代码一通过一超时的原因分析请求

我在解决LeetCode的Coin Change问题时，编写了两段逻辑相似的递归+记忆化代码，但其中一段能通过所有测试，另一段在输入coins=[186,419,83,408]、amount=6249时超时，以下是两段代码及差异原因分析：

通过的代码 #

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

超时的代码 #

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

核心差异与超时原因 #

两段代码的核心区别在于memo的更新时机：

• 通过的代码中，先初始化临时变量res = Infinity，遍历所有硬币并计算完所有子问题后，再将最终确定的结果一次性存入memo[amount]。整个计算过程中，memo[amount]始终保持初始的filter值，直到所有子问题处理完毕才写入正确结果，确保缓存的是最终有效数据。
• 超时的代码中，直接在遍历硬币的过程中逐步更新memo[amount]。这会引发致命问题：当递归调用出现循环依赖（比如计算dp(amount)时，某个子问题又递归调用回dp(amount)），此时memo[amount]已经被修改为未完成计算的中间值（不再是初始的filter），后续递归调用会直接返回这个错误的中间值，而非继续完成所有硬币的遍历计算。

这种错误的缓存机制会导致大量重复计算：缓存的不是最终正确结果，后续需要用到该值的递归分支不得不重新计算，最终时间复杂度急剧上升，在大amount输入下触发超时。

内容的提问来源于stack exchange，提问作者江定玺