10.5 Dynamic Programming

Dynamic Programming ist eine Lösungstechnik für kombinatorische Optimierungsprobleme, bei der sich die Kosten eines Problems x durch Komposition der Kosten einiger Teilprobleme x₁,x₂,...,x_k ermitteln läßt, d.h.

Seien z.B. f (x) die Kosten des kürzesten Weges vom Knoten 0 zum Knoten x in einem azyklischen Graph ((x,y) $\in$ E $\Rightarrow$ x < y) gegeben durch