Erklärung Dynamische Programmierung

Sollte die Problemlösung durch lösen von Teilproblemen abhängen, so bietet sich ein Rekursionsverfahren an. Dabei werden zunächst die Teilprobleme gelöst und daraus schließlich die Gesamtlösung konstruiert. Dies entspricht im einfachsten Fall der Induktion und den damit verbundenen Tricks (Z), (V) und (R). Anders ist jedoch, dass typischer Weise mehr als ein Teilproblem gelöst werden muss.

Wir haben bereits kennengelernt, wie Probleme durch eine geschickte Zerlegung in identische/andere Teilprobleme gelöst wurden. Nun machen wir was ähnliches, nutzen jedoch, dass Zwischenlösungen für ein und dasselbe Teilproblem mehrfach genutzt werden. Deshalb merkt man sich diese gefundenen Zwischenlösungen in einer geeigneten Datenstruktur (z.B. einer Tabelle). Diese Zwischenlösungen nutzt man dann per Table Look-up.

Für die Lösung solcher Rätsel geht man dann wie folgt vor:
Man legt sich eine (leere) Tabelle an für alle Zwischenlösungen, die man irgendwann braucht. Dann benennt man die Startwerte für die Tabelle (meist am Rand der Tabelle). Danach erarbeitet man sich Rekursionsvorschriften, um weitere Felder der Tabelle zu bestimmen. Nun werden iterativ alle Felder befüllt von denen die Rekursionsvorschriften dieses Feldes abhängen und terminiert, wenn die gewünschte Lösungsinformation vorliegt.