memoize的我的递归coinSums

我有一个基本的coinSums递归函数：memoize的我的递归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我们可以更改posi在for循环开始于0给我们的有序组合数。我需要来返回无序的组合，这就是为什么我想要保持运行组合。

来源

2016-08-16 BYC

请注意，memoization是动态编程中的一项基本技术，因为如果以前使用相同参数调用它，可以*防止*递归。你提到宁愿保留递归，但是它不会是动态编程。 –

我不知道整个问题，但我认为你应该使用'位掩码'方法来解决这个问题。 –

1.如果你正在寻找memoization这里是链接https://addyosmani.com/blog/faster-javascript-memoization/ 2.在JS中，函数也是一个对象，所以你不必声明一个新的对象来缓存值。相反，您可以使用functionName [input]来存储当前输入的输出。 3. var memo = {}是一个对象，用于存储/缓存特定输入的结果。 – Jay

恐怕你的要求是不可能满足，除非你想使用记忆化了的 coinSums本身muliple用途 - 在您呼叫subroutine 与总是不同的参数设置前者的单个应用程序，以及一个使他们的独特之处currentCombo，我认为不能“从抽象” memoizing的时候，因为它是整个算法的核心...

你可以做的是收集这种output东西用自上而下的递归，这对于记忆是“好的”，尽管这可能是你已经知道的......

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... 
}

来源

2016-08-16 17:48:46 dercz

是的，我想通了。但感谢您的帮助和想法！ – BYC

memoize的我的递归coinSums

回答

相关问题