Dynamische Programmierung: Es ist nicht das, was Sie denken

Der Begriff „dynamische Programmierung“ in Algorithmusstudien führt oft zu Verwirrung. „Dynamisch“ bezieht sich nicht auf seine Veränderlichkeit, sondern auf den Planungsprozess des „Programmierens“, der aus den 1950er Jahren stammt, als Ingenieure Bauprojekte als „Prozessplanung“ planten. In der Informatik bedeutet dynamische Programmierung, die Reihenfolge der Teilschritte zu planen, die erforderlich sind, um ein Problem zu lösen. Beispielsweise ist bei der Berechnung der Fibonacci-Sequenz das „Programm“ die Abfolge der Schritte zur Berechnung von fib(2) bis fib(10) in Abhängigkeitsreihenfolge. Dies kann von oben nach unten oder von unten nach oben geplant werden; der endgültige Plan ist derselbe, und beide werden als dynamische Programmierung betrachtet. Richard Bellman prägte den Begriff, um die Abneigung eines Verteidigungsministers gegen „mathematische Forschung“ zu vermeiden, und wählte geschickt „dynamische Programmierung“, da das Adjektiv „dynamisch“ nicht abwertend verwendet werden kann.