硬币找零运行超时

Question

我试图解决硬币找零的问题。我用了两段相似的代码，但结果是一个通过了，另一个运行超时。我想知道为什么这两段相似的代码有两种不同的结果，请解释一下原理。

1.通过一项：

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);
}

2. 一次运行超时：

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);
}

Answer 1

有两个问题：

• 此说法更新是错误的：

  memo[amount] = Math.min(memo[amount], subAmount + 1);
  

  ...因为这还不能保证是正确的结果。只有当您完成循环尝试所有可能的硬币后才能知道正确的结果。但是因为您使用中间结果更新

  memo[amount]

  ，这还不是最佳的，所以在更深的递归树中函数的执行将遇到这个临时记忆值并认为它是最终的 - 这是错误的。

• 当达到一定数量没有解决方案时，您的代码将使

  memo[amount]

  等于

  filter

  ，这意味着它被视为 not 已记忆。这就是相同数量的指数执行次数和最终超时的原因。好的代码版本会在这种情况下放置

  Infinity

  ，这将使该情况的记忆有效。