"Diejenigen, die die Vergangenheit vergessen, sind gezwungen sie zu wiederholen", Dynamische Programmierung

Die Dynamische Programmierung ist eine Methode, um ein komplexes Problem zu lösen, bei der dieses Problem in kleinere einfachere Unterprobleme aufgeteilt wird. Die Lösung dieser Unterprobleme wird nur einmal berechnet und sie wird in einer speziellen Datenstruktur im Hauptspeicher aufbewahrt (Array, Matrix, usw).

Jede Lösung dieser Unterprobleme ist indexiert in einer gewissen Weise, typischerweise über die Input-Werte des Problems, so dass das Wiederauffinden der Lösung einfach geschieht. Das nächste Mal, dass das Unterproblem wieder auftaucht, anstatt dass man die Lösung nochmals berechnet, wird sie einfach aus der Datenstruktur wieder geholt. So wird Rechenzeit gespart.

Zum Beispiel, die Erzeugung eines phylogenetischen Baums, einmal dass das DNA bekannt ist, kann einfach mit dynamischer Programmierung gemacht werden:

Klicke hier, um eine vollständige Liste der Probleme zu sehen, die mit dynamischer Programmierung gelöst werden können.