Algorithmen der dynamischen Programmierung kommen bei Optimierungsproblemen zur Anwendung, bei denen das Endergebnis aus einer unbekannten Kombination von vielen, nicht notwendigerweise unabhängigen, Teilergebnissen berechnet werden muss.
Um sich bei der Lösung kostspielige Rekursionen ohne Wiederverwendung von schon berechneten Zwischenlösungen zu ersparen, werden einfach sämtliche Teilergebnisse im Voraus berechnet und in einer Tabellen oder Liste gespeichert. Dabei ist noch das Problem zu lösen, wie die Teilergebnisse geeignet indiziert werden. Das Endergebnis ergibt sich dann im Enddurchlauf indem die optimale Verkettung von Teillösungen durchlaufen und diese Teillösungen zusammengerechnet werden.
Die Grundprinzipien der dynamischen Programmierung wurde zwar schon in den ??er Jahren formuliert, ihre Hauptanwendung fanden sie jedoch erst bei den Sequenz-Alignment Problemen der Bioinformatik.
Siehe auch: Divide and Conquer (Teile und Herrsche) - Branch and Bound - Backtracking - Greedy-Verfahren - ...