Dynamic Programming
Dynamische Programmierung zerlegt ein Problem in überlappende Teilprobleme und speichert deren Lösungen, um Neuberechnungen zu vermeiden; gelöst wird bottom-up oder top-down (Memoisation).
Zweck
Optimierungsprobleme mit optimaler Teilstruktur und überlappenden Teilproblemen effizient lösen.
Mechanismus
Die optimale Teilstruktur identifizieren: Die optimale Lösung enthält optimale Lösungen von Teilproblemen. Bottom-up: die Tabelle in aufsteigender Problemgröße füllen. Top-down: Rekursion mit Memoisation. Klassiker: Rucksackproblem, längste gemeinsame Teilfolge, Editierdistanz, Matrixkettenmultiplikation.
Anwendungsfälle
- Algorithmenentwurf
- Optimierungsprobleme
- Sequenzanalyse