Динамическое программирование: Оптимизация через перекрытие подзадач
Несмотря на пугающее название (слово «программирование» здесь означает «табличное планирование», а не написание кода), динамическое программирование (ДП) — это один из самых элегантных математических методов оптимизации алгоритмов. Разработанный Ричардом Беллманом в 1950-х годах, этот метод позволяет превратить задачи с экспоненциальной вычислительной сложностью (которые компьютер не решит и за миллион лет) в задачи с полиномиальной сложностью, решаемые за доли секунды.
Динамическое программирование применимо, если решаемая задача обладает двумя обязательными свойствами:
- Оптимальная подструктура (Принцип оптимальности Беллмана): оптимальное решение большой задачи может быть составлено из оптимальных решений её подзадач. Если мы ищем кратчайший путь из города А в город В через город Б, то часть пути от А до Б также должна быть кратчайшей из всех возможных.
- Перекрывающиеся подзадачи: рекурсивный алгоритм снова и снова решает одни и те же мелкие задачи. При вычислении 10-го числа Фибоначчи наивной рекурсией функция вычисления 3-го числа вызывается 21 раз!
Суть ДП заключается в том, чтобы решать каждую уникальную подзадачу ровно один раз и сохранять результат в память (массив или хеш-таблицу). Существуют два подхода к реализации:
1. Нисходящий подход (Мемоизация, Top-Down): мы пишем обычную рекурсивную функцию, но перед вычислением проверяем, нет ли уже готового ответа в нашем «кэше». Если есть — сразу возвращаем его. Это очень легко реализовать поверх готовой рекурсии.
2. Восходящий подход (Табуляция, Bottom-Up): мы вообще отказываемся от рекурсии. Мы создаем таблицу (массив) и начинаем заполнять ее с самых мелких, базовых случаев, постепенно поднимаясь к нужной нам большой задаче. В табличном подходе часто можно экономить память, храня только предыдущую строку матрицы.
Классические задачи, решаемые методом ДП, регулярно встречаются на собеседованиях и в реальных проектах:
- Задача о рюкзаке (0/1 Knapsack): как набрать предметов максимальной стоимости так, чтобы их вес не превысил вместимость рюкзака (базовая задача криптографии и логистики).
- Расстояние Левенштейна (Редакционное расстояние): минимальное количество операций вставки, удаления и замены символов, чтобы превратить одну строку в другую (основа проверки орфографии и сравнения ДНК в биоинформатике).
- Алгоритм Флойда-Уоршелла: нахождение кратчайших путей между всеми парами вершин в ориентированном взвешенном графе.
ДП — это не просто алгоритм, это математический способ мышления, искусство поиска правильного состояния системы и формулы перехода между этими состояниями.
