Dynamische Programmierung

Kurz: Dynamische Programmierung löst ein großes Problem, indem sie es in überlappende Teilprobleme zerlegt, jedes Teilproblem nur einmal löst und die Ergebnisse speichert.

Genauer: Sie lohnt sich, wenn ein Problem optimale Teilstrukturen hat und dieselben Teilprobleme mehrfach auftreten. Statt exponentiell viele Fälle durchzuprobieren, füllt man eine Tabelle von kleinen zu großen Teilproblemen (bottom-up) oder merkt sich Zwischenergebnisse in einer rekursiven Lösung (Memoization, top-down).

Im Detail

Beispiel: Münzwechsel

Wie viele Münzen braucht man mindestens, um einen Betrag zu bezahlen?

def min_muenzen(betrag, muenzen):
    unendlich = float("inf")
    tabelle = [0] + [unendlich] * betrag
    for b in range(1, betrag + 1):
        for m in muenzen:
            if m <= b:
                tabelle[b] = min(tabelle[b], tabelle[b - m] + 1)
    return tabelle[betrag] if tabelle[betrag] != unendlich else -1
 
print(min_muenzen(11, [1, 2, 5]))    # 3  (5 + 5 + 1)
print(min_muenzen(7, [2, 4]))        # -1 (nicht möglich)

tabelle[b] enthält die Mindestzahl Münzen für den Betrag b; jeder Eintrag baut auf kleineren auf.

Weitere klassische Probleme

• Rucksackproblem: Wertvollste Auswahl bei begrenzter Tragkraft.
• Längste gemeinsame Teilfolge (Diff-Werkzeuge) und Editierabstand (Rechtschreibkorrektur).
• Kürzeste Wege (Bellman-Ford, Floyd-Warshall) in Graphen.
• Fibonacci-Zahlen als einfachstes Beispiel.

Abgrenzung

Anders als „Teile und herrsche“ (z. B. Mergesort), wo sich die Teilprobleme nicht überlappen, nutzt dynamische Programmierung gerade die Überlappung aus. Der Name stammt von Richard Bellman und hat mit „dynamisch“ im Sinne von dynamischer Typisierung nichts zu tun.

Siehe auch: Memoization, Rekursion, Algorithmen, Big-O-Notation