Dynamische Programmierung

Einfache Sprache

Dynamische Programmierung ist eine Methode zum Lösen von Problem durch das Aufteilen in Teilprobleme und das Speichern von Zwischenresultaten. In der Praxis wird eine Lösung eines Problems rekursiv definiert und Teillösungen schrittweise in einer Tabelle aufgeführt. Es werden also erst Werte am Rekursionsende berechnet. Diese werden dann weiterverwendet.

Idee Dynamische Programmierung

Zwei Voraussetzungen (auch als Optimalitätsprinzip von Bellman bekannt) müssen erfüllt sein, damit Dynamische Programmierung erfolgreich eingesetzt werden kann:

1. Das Problem besteht aus vielen gleichartigen Teilproblemen.
2. Eine optimale Lösung des Problems sich aus optimalen Lösungen der Teilprobleme zusammensetzt.

Example

Ein Beispiel ist die Berechnung von Binomialkoeffizienten.