COINCHANGE: Dynamische Programmierung O (N) Komplexität

Question

Ich versuche, das folgende Problem zu lösen:

Sie sind eine Reihe von Münzen gegeben S. Auf wie viele Arten kann man Summe N Sie machen unter der Annahme haben unendliche Menge von jedem Münze im Set.

Hinweis: Münzen im Set S werden einzigartig sein. Die erwartete Raumkomplexität dieses Problems ist O (N). Beachten Sie, dass die Antwort überlaufen kann. Also, geben uns die Antwort% 1000007

Ich habe folgende Lösung 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; 
} 

Aber ich immer noch nicht die Anforderungen erfüllt werden: „Teilweise Richtige Antwort Machen Sie Ihre Lösung effizienter“

Wissen Sie, was dazu führen könnte, dass dieser Code nicht O (N) komplex ist?

Answer 1

Ich bin mir ziemlich sicher, es könnte sein, dass Sie rekursiv aufrufen verwenden Sie() in einer for-Schleife, die O (n) hat. Im ersten Lauf rufst du use() a.size() mal, einmal für jeden Index in a, also ist das mindestens O (n^2), oder?

Können Sie es Zeile für Zeile debuggen, um vielleicht zu sehen, wie oft Sie verwenden()? Oder sogar für jetzt nur einen Zähler jedes Mal erhöhen, wenn use() aufgerufen wird, damit Sie eine Vorstellung davon haben, wie viele Läufe Sie durchlaufen.

Alle deine anderen Methoden hier sind O (1) (denke ich), also habe ich das Gefühl, dass es diese Schleife sein muss.

Answer 2

Das Änderungsproblem kann unter Wikipedia gefunden werden. Der Code hier ist in Python. Geeks for Geeks hat die Lösung in C/C++, die syntaktisch viel näher an Java ist. Bitte nehmen Sie sich die Zeit, das eine oder andere komplett zu lesen, um die Lösung zu verstehen.