Динамическое программирование
💻 Информатика · 11 класс
Идея метода
Динамическое программирование — это приём решения задач, при котором большую задачу разбивают на меньшие подзадачи, решают каждую по одному разу и сохраняют ответы, чтобы не вычислять их заново. Метод применяют, когда подзадачи перекрываются, то есть одни и те же встречаются многократно. Сохранённые результаты складывают в таблицу.
Классический пример неэффективности — числа Фибоначчи через прямую рекурсию: одни и те же значения пересчитываются тысячи раз, и время растёт лавинообразно. Динамическое программирование устраняет эти повторы и резко ускоряет вычисления.
Два способа реализации
- Сверху вниз (с запоминанием): обычная рекурсия, но вычисленные ответы складывают в таблицу и при повторном запросе берут уже готовые.
- Снизу вверх (с заполнением таблицы): сначала решают самые маленькие подзадачи, затем по ним более крупные, постепенно доходя до исходной; рекурсия здесь не нужна.
Разбор примера
Найдём число способов подняться по лестнице из n ступеней, если за шаг можно перешагнуть на одну или на две ступени. Обозначим K(n) — число способов добраться до ступени с номером n. Тогда K(n) = K(n-1) + K(n-2), потому что на последнем шаге мы пришли либо с предыдущей ступени, либо с позапрошлой.
K(1) = 1
K(2) = 2
K(3) = K(2) + K(1) = 3
K(4) = K(3) + K(2) = 5
K(5) = K(4) + K(3) = 8Заполняя таблицу снизу вверх, мы вычисляем каждое значение ровно один раз и не повторяем работу.
Ступеней n | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
Способов K(n) | 1 | 2 | 3 | 5 | 8 |
Где применяется
Динамическое программирование решает задачу о рюкзаке, поиск наибольшей общей подпоследовательности, размен суммы монетами, подсчёт числа путей в таблице с препятствиями. Общий признак таких задач: ответ выражается через ответы меньших однотипных подзадач, и эти подзадачи повторяются.
Чем отличается от перебора
Полный перебор проверяет все возможные варианты решения, и его время растёт очень быстро — нередко удваивается с каждым новым элементом. Динамическое программирование не перебирает варианты заново, а опирается на уже сосчитанные ответы, поэтому работает гораздо быстрее. Сравним подходы на задаче о числах Фибоначчи.
| Подход | Повторные вычисления | Скорость |
|---|---|---|
| Прямая рекурсия | Очень много | Медленно, рост лавиной |
| С запоминанием | Нет | Быстро, рост линейный |
Важно отличать динамическое программирование от жадных алгоритмов: жадный делает локально лучший выбор и не всегда приходит к верному ответу, тогда как динамическое программирование рассматривает все подзадачи и гарантирует точное решение.
Частые ошибки. Неправильно задают начальные значения (базу), из-за чего вся таблица считается неверно. Ещё ошибка — применять метод там, где подзадачи не перекрываются: тогда выигрыша в скорости нет, а память тратится зря. Иногда забывают, что таблицу нужно заполнять в правильном порядке.
Кратко о главном
- Метод разбивает задачу на перекрывающиеся подзадачи и хранит их ответы.
- Реализация бывает сверху вниз (с запоминанием) и снизу вверх (таблица).
- Каждая подзадача вычисляется один раз, что ускоряет программу.
- Важно правильно задать базовые значения и порядок вычислений.