Memoize私は基本<code>coinSums</code>再帰関数を持っている

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

私は本当に（？右、k=num of coins、n=target）それはO(n^k)ランタイムを改善する方法「memoize」を把握したいと思いますが、 を再帰的に保ち、できるだけ再帰呼び出しを変更しないでください。 （私はコンボを維持する必要があり、runningSumボトムアップ アプローチ）。

私はトップダウンアプローチでそれを行う方法を知っています。どんな天才 もありますか？

PS私たちは私たちに命じた組み合わせの数を与えるために0にでforループ 着工のposそのiを変更することができます。私は、 コンボを実行し続けることを望んでいるので、順序のないコンボを返すためには が必要です。

Answer 1

私はあなたの要件は、あなたが coinSums自体のmuliple用途にメモ化を使用する場合を除き満たすことは不可能である怖いです - あなたは常に異なる引数セットでsubroutine を呼び出している元の単一のアプリケーションでは、と私はそれがアルゴリズム全体の核心であるので、私が「メモから除外する」ことができないと信じているcurrentComboです。

これを収集することは、このトップダウン再帰を使って、これはおそらくあなたが知っているものですが、メモ作成のために "いい"です。

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