Grundlagen der Informatik 2, Vorlesung 14: Dynamische Programmierung

Rekursive Darstellungen können sehr kompakte und elegante Lösungen ergeben, die im Ergebnis oft gut wartbar sind. Allerdings gibt es ein wesentliches Problem bei rekursiven Algorithmen: In vielen Fällen werden die gleichen Teilprobleme mehrfach gelöst. Das kann die Laufzeit betroffener Algorithmen so fundamental beeinflussen, dass sie für praktische Problemgrößen nicht mehr praktikabel sind. Mit der dynamischen Programmierung lernen wir eine Designstrategie für Algorithmen kennen, die darauf ausgelegt ist, diese Ineffizienz zu beheben und mit einem moderaten Mehrbedarf an Speicherplatz exponenzielle Laufzeitgewinne zu realisieren. Wir besprechen die Systematik hinter dynamischer Programmierung in einem Vier-Schritt-Verfahren und besprechen die Voraussetzungen für die Anwendbarkeit dynamischer Programmierung.