Почему функция смены монет не работает, если она включена в кэш-память? - PullRequest
Новая
       32

Почему функция смены монет не работает, если она включена в кэш-память?

0 голосов
/ 01 февраля 2019

Я пытаюсь решить классическую проблему замены монет , мой следующий код работает нормально, например, он возвращает правильное значение 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!?!?!

1 Ответ

0 голосов
/ 01 февраля 2019

Вы не должны передавать 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);
...