EMZETT.Kurz erklärt
Dynamische Programmierung löst ein großes Problem, indem sie es in überlappende Teilprobleme zerlegt, jedes Teilproblem nur einmal löst und die Ergebnisse speichert.
Genauer
Sie lohnt sich, wenn ein Problem optimale Teilstrukturen hat und dieselben Teilprobleme mehrfach auftreten. Statt exponentiell viele Fälle durchzuprobieren, füllt man eine Tabelle von kleinen zu großen Teilproblemen (bottom-up) oder merkt sich Zwischenergebnisse in einer rekursiven Lösung (Memoization, top-down).