Programowanie dynamiczne (DP)
Technika optymalizacji: podproblemy rekurencyjne rozwiązujemy raz i zapamiętujemy wyniki zamiast liczyć je od nowa. Richard Bellman (lata 50.) wybrał słowo „dynamiczne”, bo robiło wrażenie na zwierzchnikach z RAND.
Są dwie odmiany: od góry (rekurencja z memoizacją) i od dołu (iteracyjne wypełnianie tablicy). Klasyki: ciąg Fibonacciego, najdłuższy wspólny podciąg, problem plecakowy, odległość edycyjna, mnożenie łańcucha macierzy.
DP działa, gdy problem ma optymalną podstrukturę (duże rozwiązanie składa się z małych) i nakładające się podproblemy (te same pojawiają się wielokrotnie). Konkurenci: dziel i rządź (bez nakładania się) oraz algorytmy zachłanne.