Dynamische Programmierung (DP) ist ein Algorithmus-Paradigma für Probleme, die sich in überlappende Teilprobleme zerlegen lassen. Statt dieselben Teilprobleme immer wieder neu zu berechnen, wird jede Teillösung einmal berechnet und gespeichert — dadurch sinkt die Laufzeit oft von exponentiell auf polynomiell.
Zwei Varianten
- Top-down (Memoization): Das Problem wird rekursiv gelöst, und jede berechnete Teillösung wird in einer Tabelle (Cache) abgelegt. Beim erneuten Bedarf wird sie direkt abgerufen — die Rekursion bleibt erhalten, nur die Wiederholung entfällt.
- Bottom-up (Tabellierung): Die Teilprobleme werden von klein nach groß gelöst und die Ergebnisse zeilenweise in einer Tabelle aufgebaut, bis das Gesamtproblem gelöst ist.
Klassische Anwendungen
Fibonacci-Zahlen und Fakultäten lernen fast jede Einführung kennen. Wichtige praktische Beispiele sind das Rucksackproblem, die Berechnung der Editierdistanz in Textvergleichen, der Bellman-Ford-Algorithmus mit seinen Relaxations-Runden sowie viele Optimierungsprobleme in der Wirtschaft. Auch der Sortieralgorithmus-Entwurf und die Laufzeitanalyse von Algorithmen profitieren von DP-Ideen.
Abgrenzung zu anderen Paradigmen
Beim Divide-and-Conquer (z.B. Mergesort) überlappen sich die Teilprobleme nicht — jede Teillösung wird genau einmal gebraucht, ein Cache ist unnötig. Der Greedy-Algorithmus trifft dagegen nur eine einzige lokale Entscheidung pro Schritt und vergleicht keine Teilprobleme; DP wägt alle Möglichkeiten ab und ist damit allgemeiner, aber oft aufwendiger. Die Wahl des passenden Paradigmas hängt von der Struktur des konkreten Problems ab und gehört zu den Grundlagen der Algorithmik.
Kurz zusammengefasst
- Überlappende Teilprobleme werden einmal gelöst und gespeichert
- Memoization (Top-down) oder Tabellierung (Bottom-up)
- Typische Anwendungen: Fibonacci, Rucksack, Editierdistanz, Bellman-Ford
- Abgrenzung: Greedy wählt nur lokal, Divide-and-Conquer teilt ohne Überlappung