Dynamische Programmierung: Fibonacci, Rucksack und Memoization

Kurz: Dynamische Programmierung löst Probleme mit überlappenden Teilproblemen, indem sie Zwischenergebnisse speichert statt neu zu berechnen; so werden exponentielle Rechnungen zu polynomiellen.

Genauer: Wenn eine rekursive Lösung dieselben Teilprobleme immer wieder löst, speichert man die Ergebnisse. Zwei Wege: Memoization (Top-down: Rekursion + Cache) und Tabellierung (Bottom-up: Tabelle füllen).

Im Detail

Beispiel Fibonacci

fib(n) = fib(n−1) + fib(n−2). Naiv rekursiv wird fib(40) über 300 Millionen Aufrufe (exponentiell, O(2ⁿ)), weil Teilwerte mehrfach berechnet werden.

from functools import lru_cache
 
@lru_cache(maxsize=None)
def fib(n):                 # Memoization: O(n)
    return n if n < 2 else fib(n - 1) + fib(n - 2)
 
def fib_tab(n):             # Tabellierung/Bottom-up: O(n), O(1) Platz
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a

Tiefe Rekursion erreicht in Python das Rekursionslimit; Bottom-up ist dann besser.

Wann ist DP anwendbar?

Zwei Eigenschaften: Optimale Teilstruktur (Lösung setzt sich aus optimalen Teillösungen zusammen) und überlappende Teilprobleme. Vorgehen: 1) Zustand definieren (was beschreibt ein Teilproblem?), 2) Rekurrenz/Übergang formulieren, 3) Basisfälle, 4) Reihenfolge der Berechnung (Tabelle), 5) Antwort auslesen, ggf. Rekonstruktion des Weges. Greedy-Algorithmen sind schneller, aber nur korrekt, wenn die Greedy-Wahl beweisbar optimal ist; DP ist sicherer.

Klassiker

• Rucksackproblem (0/1): Gegenstände mit Gewicht/Wert, Kapazität W: dp[i][w] = max(dp[i−1][w], dp[i−1][w−gew_i] + wert_i); Zeit O(n·W) (pseudopolynomiell).
• Kleinste Münzanzahl (Coin Change): dp[x] = 1 + min(dp[x − m]).
• Längste gemeinsame Teilfolge (LCS) und Editierdistanz (Levenshtein): Basis von diff, Rechtschreibkorrektur, DNA-Vergleich.
• Kürzeste Wege (Bellman-Ford, Floyd-Warshall).
• Treppenstufen, Zählprobleme, Matrixketten, Optimale Suchbäume, Viterbi-Algorithmus (Spracherkennung).

Praxis und Prüfung

• Tabelle zeichnen und von Hand ausfüllen: so entsteht das Verständnis.
• Auf Platz sparen: oft reicht die letzte Zeile/zwei Werte.
• Speicher/Zeit abwägen; O(n·W) kann groß werden.
• Typische Fehler: falsche Basisfälle, Off-by-one, Reihenfolge der Schleifen.
• In Programmierwettbewerben, Optimierung (Routen, Schnitte, Planung), Bioinformatik, Textvergleich.
• Verwandt: Rekursion, Backtracking (probiert alle Wege), Greedy, Divide and Conquer (Teilprobleme überlappen nicht).

Siehe auch: Rekursion, Greedy-Algorithmen, Big-O-Notation, Backtracking