Dynamic programming (DP)
Optimerings-teknik: lös rekursiva delproblem en gång och cacha resultaten istället för att räkna om. Richard Bellman (1950-talet) — "dynamic" var bara för att låta imponerande för RAND-managers.
Två former: top-down (rekursion + memoization) och bottom-up (iterativ tabellfyllning). Klassiska problem: Fibonacci, Longest Common Subsequence, knapsack, edit distance, matrix chain multiplication.
DP funkar när problemet har optimal substruktur (lösningen på det stora är lösningar på de små) och överlappande delproblem (samma delproblem stöter du på flera gånger). Konkurrent: divide-and-conquer (utan överlapp), greedy.