COINCHANGE：動的計画法O（N）の複雑

Question

私は、次のような問題を解決しようとしています：

あなたはあなたは合計を作ることができますどのように多くの方法でコインS.のセットを与えられたNは、各の無限の量を持っていると仮定していますセットのコイン。

注：セットSのコインは一意になります。この問題の予想される空間複雑度はO（N）です。 答えがオーバーフローする可能性があることに注意してください。 「部分的に正解ソリューションをより効率的に」

：だから、私はDP

HashMap<Integer, HashMap<Integer, Integer>> memo = new HashMap<>(); 
public int coinchange2(List<Integer> a, int b) { 
    return use(a, 0, b); 
} 

private int use(List<Integer> a, Integer index, int n) { 
    if(memo.containsKey(a.get(index))) { 
     if(memo.get(a.get(index)).containsKey(n)) { 
      return memo.get(a.get(index)).get(n); 
     } 
    } 
    if(n == 0 && a.get(index)>=0) { 
     return 1; 
    } 
    if((n > 0 && a.get(index) == 0) || n < 0) { 
     return 0; 
    } 
    int nbWays = 0; 
    for(int i = index; i < a.size(); i++) { 
     nbWays += use(a, i, n - a.get(i))%1000007; 
    } 

    if(!memo.containsKey(a.get(index))) { 
     memo.put(a.get(index), new HashMap<Integer, Integer>()); 
    } 
    nbWays = nbWays % 1000007; 
    memo.get(a.get(index)).put(n, nbWays); 
    return nbWays; 
} 

を使用して、以下のソリューションを持っている。しかし、私はまだ要件を満たしていない私たちに答え％1000007

を与えます

このコードがO（N）の複雑さにならない原因を知っていますか？

Answer 1

O（n）を持つforループでuse（）を再帰的に呼び出すことができるのは間違いありません。最初の実行では、aの各インデックスに対してuse（）a.size（）回を1回呼び出すので、これは少なくともO（n^2）です。

use（）を何回呼び出しても、それを1行ずつデバッグできますか？あるいは、今のところuse（）が呼び出されるたびにカウンタをインクリメントするだけで、実行するランの数を知ることができます。

ここのあなたの他のすべての方法はO（1）（私は思う）だから、私はそれがループであるように感じる。

Answer 2

変更の問題はWikipediaにあります。ここのコードはPythonで書かれています。 Geeks for Geeksには、C/C++のソリューションがあります。これは、Javaと構文的に非常に近いものです。解決策を理解するために、時間をかけてどちらか一方を完全に読んでください。