Динамическое программирование

Два подхода

• 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);
}

Когда применять

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