记住我的递归 coinSums

Question

我有一个基本的coinSums递归函数：

function coinSums(total) {      
    var coins = [1, 5, 10, 25];
    var output = [];
    var memo={} <--the only part im sure about :)
    function subroutine(pos, runningSum, currentCombo) {
        if (total === runningSum) {
            return output.push(currentCombo)
        } else if (total < runningSum) {
            return false
        } else
            for (var i = pos; i < coins.length; i++) {
                subroutine(i, runningSum + coins[i], currentCombo.concat(coins[i]))
            }
    }
    subroutine(0, 0, [])
    return output.length; }

我真的很想找到一种方法 'memoize' 它来改进 O(n^k) 运行时（k=num of coins、n=target，对吗？），但保留它递归而不是尽可能少地改变递归调用。（我需要保持组合和 runningSum 自下而上方法）。

我知道如何使用自上而下的方法来做到这一点。任何天才有什么想法吗？

ps我们可以在for循环中改变pos即i 从 0 开始给我们有序组合的数量。我需要到 return 无序组合，这就是为什么我要维护运行连击。

Answer 1

恐怕你的要求是不可能满足的，除非你想使用 memoization 来多次使用 coinSums 本身——在您调用的前者的单个应用程序中 subroutine 总是不同的参数集，使它们独一无二的是currentCombo，我认为在记忆时不能是"abstracted from"，因为它是整个算法的核心...

你可以做的是用自上而下的递归来收集这个 output 东西，这是 "nice" 用于记忆，虽然这可能是你已经知道的...

function coinSums(total) {
    /// "cache":
    var _coinSumsMem_ = {};
    var lookupCoins = function(total,pos) {
        return _coinSumsMem_[[total,pos]];
    };
    var memoizeCoins=function(total,pos, coins) {
        _coinSumsMem_[[total,pos]]
            = coins.map(function(xs) {return xs.slice();}); /// a clone!
    };
    /// "computation":
    var coinsAvailable = [1,5,10,20];    
    findAll = function(total, pos) {
        if(total<0 || pos==coinsAvailable.length) return [];
        else if(total==0) return [[]];
        var result = lookupCoins(total,pos);
        if(result == undefined) {
            var oneWaySums = findAll(total-coinsAvailable[pos], pos);
            oneWaySums.map(function(xs) {xs.push(coinsAvailable[pos]);});
            var otherWaySums = findAll(total, pos+1);
            result = oneWaySums.concat(otherWaySums);
            memoizeCoins(total,pos, result);
        }
        return result;
    };
    return findAll(total,0).length; /// or without length...
}

Answer 2

这是一种使用动态规划的方法。有关该方法的更多详细信息，请观看此视频 https://www.youtube.com/watch?v=jaNZ83Q3QGc。

function coinsSum(amount) {
  const coins = [1, 5, 10, 25]
  const combinations = Array(amount + 1).fill(0);
  combinations[0] = 1;
  let count = 0;
  while (count < coins.length) {
    const coin = coins[count];
    for (let i = coin; i < combinations.length; i++) {
      if (amount >= coin) combinations[i] += combinations[i - coin];
    }
    count++;
  }
  return combinations.pop();
}

记住我的递归 coinSums

Memoize my recursive coinSums

javascript

recursion

dynamic-programming

memoization