Dynamic programming (DP) — техника решения задач путём разбиения на подзадачи и сохранения результатов. Если подзадачи перекрываются (одна и та же подзадача решается много раз), DP кеширует результат и не пересчитывает. Два подхода: top-down (рекурсия + мемоизация) и bottom-up (заполняешь таблицу от малых подзадач к большим). Классика: числа Фибоначчи, задача о рюкзаке, longest common subsequence. В Go DP обычно — просто массив или map для кеша. Сложность DP — придумать формулу перехода.

Что такое dynamic programming?