Ein Verfahren zur Lösung komplexer Probleme durch Zerlegung in sich überschneidende Teilprobleme und das Speichern ihrer Lösungen (mittels Memoisierung oder Tabellierung), sodass jedes Teilproblem nur einmal gelöst wird und redundante Berechnung vermieden wird; anwendbar, wenn das Problem optimale Teilstruktur und überschneidende Teilprobleme aufweist.

Prinzip

Anwendung des Optimalitätsprinzips: Eine optimale Lösung eines Problems enthält optimale Lösungen seiner Teilprobleme; den Rechneraufwand um Zustandsrepräsentation, Rekurrenzrelation und Wiederverwendung berechneter Teilergebnisse organisieren.

Demonstration

Berechnung der n-ten Fibonacci-Zahl durch Speicherung früherer Fibonacci-Werte (Memoisierung oder Bottom-up-Tabelle): statt exponentieller Rekursion berechnet man F(0), F(1), …, F(n) jeweils einmal und verwendet sie wieder. Bei Optimierung wird das 0/1-Rucksackproblem durch Auffüllen einer Tabelle der besten Werte für Kapazität und Prefix von Gegenständen gelöst, um dieselben Kombinationen nicht mehrfach zu prüfen.

Fehlanwendung

Einsatz von dynamischer Programmierung bei Problemen ohne optimale Teilstruktur (z. B. wenn lokale optimale Entscheidungen nicht zu globalen Optima führen) oder bei Problemen mit extrem großem Zustandsraum ohne Kompression, was zu falschen Ergebnissen oder unvertretbarem Speicherbedarf führt.

Konsequenz

Wenn anwendbar, können naive exponentielle Suchverfahren häufig zu Algorithmen mit polynomieller Laufzeit reduziert werden; Zeit wird gegen Speicher getauscht (Memo-Tabellen), und Lösungen sind innerhalb der gewählten Repräsentation reproduzierbar und exakt.

Umkehrung

Gierige Verfahren oder klassische Divide-and-Conquer-Methoden, die Teilproblemlösungen nicht wiederverwenden und lokal optimale Entscheidungen treffen, ohne globale Optimalität sicherzustellen; sie sind manchmal schneller, können aber falsch sein, wenn globale Koordination nötig ist.

Abgrenzung

Gilt für diskrete Probleme mit wohldefinierten Zuständen und Rekurrenzen; schließt Probleme ohne optimale Teilstruktur oder solche ein, deren Zustände nicht kompakt darstellbar sind (z. B. bestimmte nicht-markovschen oder hochdimensionalen kontinuierlichen Probleme) sowie Fälle, in denen der Speicher-/Zeithandel untragbar ist.

Semantische Spannung

Spannung zwischen Memoisierung (top-down Caching) und Tabellierung (bottom-up Iteration) sowie zwischen dynamischer Programmierung und herkömmlichem Divide-and-Conquer: Beide zerlegen Aufgaben, unterscheiden sich jedoch in Wiederverwendungsstrategie und Reihenfolge.

Synthese

Dynamische Programmierung wandelt eine Rekurrenz oder Zustandszerlegung systematisch in eine Berechnung um, die gelöste Teilprobleme wiederverwendet und damit Speicher gegen Zeit tauscht; praktisch erfordert dies das Entwerfen von Zuständen, Übergängen und Speichergrenzen.