Dinamik programlama (DP)
Optimizasyon tekniği: özyinelemeli alt problemleri bir kez çözüp sonuçları önbelleğe alır, yeniden hesaplamaz. Richard Bellman (1950’ler); “dinamik” sözcüğü RAND yöneticilerine etkileyici gelsin diye seçildi.
İki çeşidi var: yukarıdan aşağı (özyineleme + memoization) ve aşağıdan yukarı (yinelemeli tablo doldurma). Klasik problemler: Fibonacci, En Uzun Ortak Altdizi, sırt çantası, düzenleme mesafesi, matris zinciri çarpımı.
DP, problemin optimal alt yapıya (büyük çözüm küçüklerden kurulur) ve çakışan alt problemlere (aynı alt problem tekrar tekrar çıkar) sahip olduğu durumda işe yarar. Rakipleri: böl ve yönet (çakışma yok) ve açgözlü algoritmalar.