Combination Sum (Kombinationssumme)
Angenommen, wir haben den Zielwert
N und ein Array von erlaubten positiven Zahlen. Unsere Aufgabe besteht darin, die Anzahl der Möglichkeiten zu ermitteln, wie sich N als Summe dieser Zahlen ausdrücken lässt.Wenn zum Beispiel die zulässigen Werte
[1, 2, 3] sind und die Zahl N gleich 4 ist, dann können diese Zahlen auf 7 verschiedene Arten summiert werden:Alle 7 Möglichkeiten, 1, 2 und 3 zu summieren, um 4 zu erhalten
- 1 + 1 + 1 + 1
- 1 + 1 + 2
- 1 + 2 + 1
- 2 + 1 + 1
- 1 + 3
- 3 + 1
- 2 + 2
Dies ist ein klassisches Problem der Dynamischen Programmierung, das sich durch die Verwendung eines Zustands
d[sum] lösen lässt, der die Anzahl aller möglichen Weisen repräsentiert, wie man sum mithilfe der erlaubten Zahlen bilden kann:N = ...
nums = [...]
d = [0] * (N + 1) # d[i] = alle Kombinationen, die sich zu i summieren
d[0] = 1 # Es gibt eine Möglichkeit, 0 zu erhalten: keine Zahlen wählen
for i in range(1, N + 1):
for num in nums:
if i - num >= 0:
d[i] += d[i - num]
print(d[N])Hier bedeutet
d[i], wie viele Möglichkeiten es gibt, die Zahl i mithilfe der Zahlen in nums zu erzeugen. Zu Beginn wird alles auf 0 gesetzt, außer d[0], das auf 1 steht, weil 0 genau auf eine Weise erzeugt werden kann – indem man keine Zahlen nimmt. Für alle anderen Werte wird geprüft, inwieweit sie mithilfe der erlaubten Zahlen aufgebaut werden können.Beispielsweise, wenn wir wissen, dass sich die Zahl 11 (
d[11]) bereits auf 5 verschiedene Arten bilden lässt und die Zahl 8 (d[8]) auf 3 verschiedene Arten, dann erlaubt uns das Vorhandensein der Zahl 3 in nums, auch 11 noch zusätzlich über jede Möglichkeit von 8 zu bilden (indem wir 3 anhängen).Unten sieht man eine Beispielsituation mit den Eingaben
nums = [1, 2, 3] und N = 4:Simulation der oben beschriebenen Methode
d = [1, 0, 0, 0, 0]→ 1 Möglichkeit für 0, Rest ist 0
i = 1num = 1 ⇒ d[1] += d[0] ⇒ d = [1, 1, 0, 0, 0] num = 2 ⇒ i - num < 0 num = 3 ⇒ i - num < 0
i = 2num = 1 ⇒ d[2] += d[1] ⇒ d = [1, 1, 1, 0, 0] num = 2 ⇒ d[2] += d[0] ⇒ d = [1, 1, 2, 0, 0] num = 3 ⇒ i - num < 0
i = 3num = 1 ⇒ d[3] += d[2] ⇒ d = [1, 1, 2, 2, 0] num = 2 ⇒ d[3] += d[1] ⇒ d = [1, 1, 2, 3, 0] num = 3 ⇒ d[3] += d[0] ⇒ d = [1, 1, 2, 4, 0]
i = 4num = 1 ⇒ d[4] += d[3] ⇒ d = [1, 1, 2, 4, 4] num = 2 ⇒ d[4] += d[2] ⇒ d = [1, 1, 2, 4, 6] num = 3 ⇒ d[4] += d[1] ⇒ d = [1, 1, 2, 4, 7]
print(d[4])→ gibt 7 aus
Herausforderung – Dice Combinations
Wenn man einen Würfel wirft, erhält man eine Zahl zwischen 1 und 6. Die Aufgabe besteht darin, die Anzahl der Möglichkeiten zu bestimmen, eine Zielzahl
n durch die Summe solcher Würfelwürfe zu erreichen.
Eingabe
Die Eingabe besteht aus einer einzelnen ganzen Zahl
n (1 ≤ n ≤ ).Ausgabe
Das Programm soll die Anzahl der Möglichkeiten ausgeben, wie man durch Würfelwürfe die Summe
n erreichen kann. Da das Ergebnis sehr groß werden kann, soll das Resultat modulo ausgegeben werden.Beispiele
Eingabe | Ausgabe |
2 | 2 |
3 | 4 |
Erläuterung
- 2 → 1 + 1, 2
- 3 → 1 + 1 + 1, 1 + 2, 2 + 1, 3
Constraints
Time limit: 5 seconds
Memory limit: 512 MB
Output limit: 1 MB