Overview
Minimale Anzahl Münzen aus einem gegebenen Set um genau einen Zielbetrag zu erreichen.
Analogy
Wechselgeld an der Kasse herausgeben: wenigste Münzen/Scheine für exakten Betrag.
Step-by-step
- dp[0]=0; dp[i]=∞ für i=1..Betrag.
- Für jede Münze c und jeden Betrag i≥c: dp[i] = min(dp[i], dp[i-c]+1).
- Wenn dp[Betrag] noch ∞ → return -1 (unmöglich).
Visual
coins=[1,2,5], amount=11: dp=[0,1,1,2,2,1,2,2,3,3,2,3] → dp[11]=3 (5+5+1)
Common mistakes
- dp[0]=1 statt 0 initialisieren.
- Greedy (immer größte Münze) funktioniert nicht für beliebige Münzsets.
Practice questions
- Anzahl der Möglichkeiten (nicht Minimum) zählen.
- Die tatsächlich verwendeten Münzen rekonstruieren.
Time
O(Betrag × Anzahl Münzen)