Динамічне програмування

Дві підходи

• Top-down (мемоізація) — рекурсія + кеш результатів. Природніший для запису
• Bottom-up (табуляція) — ітеративно заповнюємо таблицю від базових випадків

Числа Фібоначчі

// Без DP: O(2^n)
fib(n) = fib(n-1) + fib(n-2)

// З мемоізацією: O(n)
$memo = [];
function fib(int $n): int {
  global $memo;
  if ($n <= 1) return $n;
  return $memo[$n] ??= fib($n-1) + fib($n-2);
}

Коли застосовувати

Задача має оптимальну підструктуру (оптимальне рішення складається з оптимальних підрішень) і підзадачі що перетинаються. Класичні задачі: найдовша спільна підпослідовність, задача про рюкзак, мінімальний шлях у графі.