なぜ私のシンプルなキャッシュが機能しないのですか？

Question

私は正確に（十分に速くはないが）を評価され、私は

private int CountChangeOptions(int[] coins, int j, int N) 
{ 
    if(j == 0) 
     return 0; 
    if(N == 0) 
     return 1; 
    if(j == 1) 
     return N % coins[0] == 0 ? 1 : 0; 

    int sum = 0; 
    int k = coins[j - 1]; 
    for(int i = N; i >= 0; i -= k) 
    { 
     sum += CountChangeOptions(coins, j - 1, i); 
    } 
    return sum; 
} 

を書いたコードの塊を持っています。最もcoinsためCountChangeOptions(coins, x, y)ので、アルゴリズムの過程でy、同じxで数回呼び出されるだろう、私はキャッシュ戦略_cacheが以前_cache = new int[N+1, N+1]に設定されているint?[][]ある

private int CountChangeOptions(int[] coins, int j, int N) 
{ 
    if(j == 0) 
     return 0; 
    if(N == 0) 
     return 1; 
    if(j == 1) 
     return N % coins[0] == 0 ? 1 : 0; 

    int sum = 0; 
    int k = coins[j - 1]; 
    for(int i = N; i >= 0; i -= k) 
    { 
     sum += CountOrGetFromCache(coins, j - 1, i); 
    } 
    return sum; 
} 

private int CountOrGetFromCache(int[] coins, int j, int i) 
{ 
    if(_cache[j, i] == null) 
    { 
     _cache[j, i] = CountChangeOptions(coins, j, i); 
    } 
    return (int)_cache[j, i]; 
} 

を実施することを決定しました。しかし、これは現在いくつかのテストケースで失敗しています。どんな考え？私が見

Answer 1

唯一の問題は、_CACHE変数が間違って

_cache = new int[N+1, N+1] 

の代わりに、それ以外は

_cache = new int[coins.Length+1, N+1] 

に初期化されていることで、両方のソリューションは、機能的に同じです。私は、最初の（遅い）実装には機能し、2番目の実装には失敗する機能テストケースがあるとは思わない。

私はあなたがHackerRankなどのようないくつかのウェブサイトを使用していると推測しています。最初の解決策はおそらくタイムアウトして、動作し、 。