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

Рекурсия элегантна, но часто пересчитывает одно и то же тысячи раз. Динамическое программирование — метод решения задач, которые распадаются на перекрывающиеся подзадачи: оптимальный ответ на задачу собирается из оптимальных ответов на её меньшие версии (оптимальная подструктура), а каждая подзадача решается один раз, и результат запоминается в таблице. Метод ввёл Ричард Беллман в 1950-х, и имя «динамическое» было, по его собственному признанию, скорее рабочей вывеской, чем описанием сути. В дискретной математике ступенчатый пересчёт по шагам — это вычисление по рекуррентным соотношениям: значение для шага n выражается через значения меньших шагов. Корректность переходов проверяется индукцией: база таблицы — база индукции, заполнение клетки — индукционный переход; ход такого рассуждения разбирает математическая индукция.

Классика жанра — числа Фибоначчи: определение $F_n=F_{n-1}+F_{n-2}$ скрывает ловушку наивной рекурсии — ветви дерева вызовов дублируются, и для $F_{30}$ счётчик засчитывает 1 664 079 вызовов, хотя уникальных подзадач всего тридцать. Таблица снизу вверх решает всё за 28 сложений, а числа Фибоначчи превращаются из символа экспоненциальной тупости в линейный алгоритм. Та же схема считает число путей по сетке 3×4: из левого нижнего угла в правый верхний ведут $C(7,3)=35$ путей — значение клетки есть сумма значений соседа слева и соседа снизу. Типичные грабли: применять ДП там, где подзадачи не перекрываются, — хватит обычного «разделяй и властвуй»; путать с жадностью — та берёт локально выгодный шаг без пересмотра, а ДП честно сравнивает варианты; ошибиться в порядке заполнения таблицы и обращаться к ещё не посчитанным клеткам.