时间戳

首页 > 解决方案 > 为什么我的硬币找零功能包含在记忆缓存中时不起作用？

javascript - 为什么我的硬币找零功能包含在记忆缓存中时不起作用？

问题描述

我正在尝试经典的硬币找零问题，我的以下代码工作正常，例如，它返回正确的值 3，硬币组合为 [1, 2, 5]，目标为 11。但是，当我向递归调用它会得到一个不正确的答案？我在函数调用中做错了什么？

var coinChange = function(coins, amount, totalCoins = 0, cache = {}) {
    if (cache[amount] !== undefined) return cache[amount];
    if (amount === 0) {
        return totalCoins;
    } else if (0 > amount) {
        return Number.MAX_SAFE_INTEGER;
    } else {
        let minCalls = Number.MAX_SAFE_INTEGER;
        for (let i = 0; i < coins.length; i++) {
            let recursiveCall = coinChange(coins, amount - coins[i], totalCoins + 1, cache);
            minCalls = Math.min(minCalls, recursiveCall);
        }
        const returnVal = (minCalls === Number.MAX_SAFE_INTEGER) ? -1 : minCalls;
        return cache[amount] = returnVal;
    }
}

console.log(coinChange([1, 2, 5], 11)); // This ends up outputting 7!?!?!

标签： javascriptrecursionmemoizationcoin-change

解决方案

您不应将totalCoins其作为函数参数传递给递归调用，因为这是您要计算的内容。相反，它应该计算如下

var coinChange = function(coins, amount, cache = {}) {
    if (cache[amount] !== undefined) return cache[amount];
    if (amount === 0) {
        return 0;
    } else if (0 > amount) {
        return Number.MAX_SAFE_INTEGER;
    } else {
        let minCalls = Number.MAX_SAFE_INTEGER;
        for (let i = 0; i < coins.length; i++) {
            let recursiveCall = 1 + coinChange(coins, amount - coins[i], cache);
            minCalls = Math.min(minCalls, recursiveCall);
        }
        const returnVal = (minCalls === Number.MAX_SAFE_INTEGER) ? -1 : minCalls;
        return cache[amount] = returnVal;
    }
}

console.log(coinChange([1, 2, 5], 11)); // This outputs 3

注意这一行

let recursiveCall = 1 + coinChange(coins, amount - coins[i], cache);

推荐阅读