Dynamische Programmierung
Dynamische Programmierung ist die „Kunst“, einen aktuellen Zustand auf Basis vorheriger Zustände aufzubauen. Bei vielen Berechnungen greifen wir auf bereits berechnete Werte zurück und nutzen sie weiter. Fibonacci-Zahlen sind ein anschauliches Beispiel, das sich mittels dynamischer Programmierung berechnen lässt:
Um zum Beispiel
fib(2) zu berechnen, verwenden wir fib(1) und fib(0). Dadurch erhalten wir fib(2) = 1. Für den nächsten Wert nutzen wir den bereits ermittelten Wert weiter – fib(3) = fib(2) + fib(1) = 1 + 1 = 2. Genauso ergibt sich fib(4) = fib(3) + fib(2) = 2 + 1 = 3, und fib(5) = fib(4) + fib(3) = 3 + 2 = 5 usw.In jeder Iteration wird der aktuelle Fibonacci-Wert aus den zuvor berechneten Werten ermittelt. Das lässt sich beispielsweise mit einer Liste umsetzen:
n = ...
fib = [0, 1] # fib[0] = 0, fib[1] = 1
for i in range(2, n + 1):
fib.append(fib[i - 1] + fib[i - 2])
print(fib[n])Für
n = 5 gibt das Programm 5 aus, während bei n = 7 der Wert 13 erscheint.Durch das wiederholte Nutzen vorheriger Zustände (in unserem Beispiel die vorherigen Fibonacci-Werte) entsteht das Grundprinzip der Dynamischen Programmierung.
💡
Dynamische Programmierung ist eine Technik, um den aktuellen Zustand aus den vorherigen Zuständen abzuleiten.
Challenge – Tribonacci-Zahlen
Nachdem du mit Fibonacci-Zahlen herumgespielt hast, möchtest du nun etwas Neues ausprobieren: Tribonacci-Zahlen. Sie sind wie folgt definiert:
Deine Aufgabe ist es, die
n-te Tribonacci-Zahl zu bestimmen.Eingabe
Die Eingabe enthält eine einzelne ganze Zahl
n (1 ≤ n ≤ 30).Ausgabe
Gib die
n-te Tribonacci-Zahl aus.Beispiele
Eingabe | Ausgabe |
2 | 1 |
4 | 2 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB