我有一个基本的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我们可以更改pos
i
在for
循环 开始于0给我们的有序组合数。我需要 来返回无序的组合,这就是为什么我想要保持 运行组合。
请注意,memoization是动态编程中的一项基本技术,因为如果以前使用相同参数调用它,可以*防止*递归。你提到宁愿保留递归,但是它不会是动态编程。 –
我不知道整个问题,但我认为你应该使用'位掩码'方法来解决这个问题。 –
1.如果你正在寻找memoization这里是链接https://addyosmani.com/blog/faster-javascript-memoization/ 2.在JS中,函数也是一个对象,所以你不必声明一个新的对象来缓存值。相反,您可以使用functionName [input]来存储当前输入的输出。 3. var memo = {}是一个对象,用于存储/缓存特定输入的结果。 – Jay