Динамическое программирование и мемоизация
Превращаем экспоненциальную рекурсию в линейный код, запоминая уже вычисленное
Главная идея: Многие рекурсивные решения заново решают одну и ту же подзадачу тысячи раз. Динамическое программирование (ДП) — это дисциплина решать каждую отдельную подзадачу один раз и переиспользовать ответ. Мемоизация — это способ сверху вниз: держим кэш с ключом по аргументам. Табуляция — способ снизу вверх: заполняем таблицу от самых мелких подзадач к крупным. Одна и та же рекуррента, два направления.
К концу вы сможете:
- распознавать два признака применимости ДП: перекрывающиеся подзадачи и оптимальную подструктуру,
- превращать наивную рекурсию в самописный словарь-мемо,
- использовать
functools.lru_cache, когда аргументы хешируемы, - переписывать решение сверху вниз в табуляцию снизу вверх,
- применять всё это к числам Фибоначчи, размену монет и задаче о рюкзаке 0/1,
- честно оценивать компромиссы по времени и памяти.
Это продвинутая итоговая тема. Она предполагает, что вы свободно владеете рекурсией, нотацией «О большое», замыканиями и модулем functools из более ранней темы о декораторах. Мы опираемся на них напрямую, а не пересказываем заново.
1. Когда применимо ДП? Два условия
Динамическое программирование — не приём, который можно посыпать на любую медленную функцию. Это оптимизация, которая окупается только тогда, когда у задачи есть оба свойства:
- Перекрывающиеся подзадачи. Рекурсия снова и снова запрашивает ответ на один и тот же меньший экземпляр. Если бы каждая подзадача была уникальной, кэшировать было бы нечего и ДП лишь добавило бы накладные расходы. (Обычное «разделяй и властвуй», например сортировка слиянием, не имеет перекрытий, поэтому мемоизация ей ничего не даёт.)
- Оптимальная подструктура. Оптимальный ответ для всей задачи строится из оптимальных ответов её подзадач. Именно это позволяет корректно комбинировать закэшированные результаты, а не выводить их заново.
Фибоначчи, кратчайшие пути, размен монет и рюкзак удовлетворяют обоим. Когда вы видите рекурренту, которая вызывает себя на перекрывающихся диапазонах, ДП — нужный инструмент.