Что это динамическое программирование?
ДП решает задачу комбинируя ответы на перекрывающиеся подзадачи, сохраняя каждый ответ один раз. Два обязательных свойства: перекрывающиеся подзадачи и оптимальная подструктура. Это превращает экспоненциальную рекурсию (как наивный Фибоначчи) в линейную.
Ты уже знаешь рекурсию: функция вызывает себя на меньшем входе и доверяет что ответ вернётся. Но посмотри что происходит с Фибоначчи. Чтобы получить fib(5), ты вычисляешь fib(4) и fib(3). Но fib(4) вычисляет fib(3) снова. А fib(3) вычисляет fib(2) дважды. Те же маленькие задачи решаются снова и снова — работа взрывается. Динамическое программирование это исправление: реши каждую маленькую задачу один раз, запиши ответ, и переиспользуй его. Экспоненциальная рекурсия схлопывается в прямую линию.
После этого урока ты понимаешь что это динамическое программирование (ДП): комбинирование ответов на перекрывающиеся подзадачи, сохраняя каждый ответ один раз вместо его пересчёта. Ты можешь назвать два свойства которые задача должна иметь чтобы ДП применялось — перекрывающиеся подзадачи и оптимальная подструктура — и объяснить каждое. Ты можешь увидеть в дереве рекурсии Фибоначчи почему наивная рекурсия повторяет работу (экспоненциально) тогда как ДП нет (линейно). Ты можешь отличить ДП от «разделяй и властвуй» (чьи подзадачи не перекрываются) и от жадного (который фиксирует один локальный выбор без исследования комбинаций). Ты можешь распознать задачи в форме ДП по их сигналам: «сосчитай способы», «мин/макс по выборам», «можешь ли достичь». Следующие два урока учат двум способам реализации ДП: мемоизация (урок 02) и табуляция (урок 03).
Что это динамическое программирование?
Динамическое программирование (ДП) это приём для решения задачи разбивая её на меньшие подзадачи, решая каждую подзадачу один раз, и сохраняя её ответ так что ты никогда не вычисляешь его дважды. Когда та же подзадача появляется снова, ты смотришь сохранённый ответ вместо повторения работы.
Это вся идея: реши один раз, запомни, переиспользуй. ДП это рекурсия плюс память.
Два обязательных свойства
ДП помогает только когда задача имеет оба из них:
- Перекрывающиеся подзадачи. Наивное рекурсивное решение решает ту же подзадачу много раз. Если бы каждая подзадача была уникальной, нечего было бы запоминать и ДП не помогло бы.
- Оптимальная подструктура. Оптимальный ответ на всю задачу может быть построен из оптимальных ответов на её подзадачи. Если склеивание лучших кусков не даёт лучшее целое, ты не можешь комбинировать ответы подзадач, и ДП не применяется.
Если любое из свойств отсутствует, ДП это неверный инструмент.
Свойство 1: перекрывающиеся подзадачи (мотивация)
Посмотри на наивный рекурсивный Фибоначчи. fib(n) = fib(n-1) + fib(n-2), с fib(0) = 0 и fib(1) = 1. Нарисуй дерево вызовов для fib(5):
fib(5)
/ \
fib(4) fib(3)
/ \ / \
fib(3) fib(2) fib(2) fib(1)
/ \ / \ / \
fib(2) fib(1) fib(1) fib(0) fib(1) fib(0)
/ \
fib(1) fib(0)Сосчитай повторы: fib(3) вычислен 2 раза, fib(2) 3 раза, fib(1) 5 раз, fib(0) 3 раза. Дерево ветвится надвое на каждом шаге, так его размер примерно удваивается на каждом уровне. Это экспоненциальный рост — та же горстка подзадач, пересчитываемая снова и снова.
Свойство 2: оптимальная подструктура
Фибоначчи также имеет оптимальную подструктуру: ответ для n строится прямо из ответов для n-1 и n-2. Есть только один способ вычислить fib(n) из его частей, так любые корректные fib(n-1) и fib(n-2) дают корректный fib(n). Для задач оптимизации (кратчайший путь, наибольшая подпоследовательность), это свойство говорит: лучшее решение целого содержит лучшие решения его подчастей.
Исправление ДП
Есть только n+1 различных подзадач Фибоначчи: fib(0), fib(1), …, fib(n). Дерево рекурсии имеет тысячи узлов, но они отвечают на ту же горстку вопросов. ДП вычисляет каждый из этих n+1 ответов ровно один раз и переиспользует их. Экспоненциальная работа становится линейной:
Naive recursion: computes fib(k) many times -> ~2^n calls
Dynamic prog.: computes fib(k) exactly once -> n+1 distinct answersДП против «разделяй и властвуй»
Оба разбивают задачу на подзадачи. Разница в том, перекрываются ли подзадачи.
- Разделяй и властвуй (сортировка слиянием, бинарный поиск): подзадачи непересекающиеся. Сортировка слиянием разбивает массив на две половины которые не разделяют элементов. Ничего не пересчитывается, так нечего кэшировать — простая рекурсия уже эффективна.
- Динамическое программирование: подзадачи перекрываются. Та же подзадача появляется снова в разных ветвях, так кэширование её ответа это то что делает ДП быстрым.
Правило большого пальца: если кэширование ответов подзадач сэкономило бы работу, это ДП; если каждая подзадача уникальна, это «разделяй и властвуй».
ДП против жадного
Оба могут решать задачи оптимизации, но они выбирают по-разному.
- Жадный фиксирует единственный лучше всего выглядящий выбор на каждом шаге и никогда не пересматривает. Он быстр, но он находит глобальный оптимум только на задачах где локальные выборы гарантированно безопасны.
- Динамическое программирование рассматривает все способы комбинировать ответы подзадач и хранит лучший. Оно исследует комбинации которые жадный пропускает, так оно решает задачи где никакое единое локальное правило не всегда корректно — ценой большей работы.
Распознавание задачи ДП
Задача часто ДП когда ты видишь:
- «Сосчитай способы» сделать что-то (число путей, число декодирований).
- «Найди мин / макс» по множеству выборов (минимум монет, наибольшая возрастающая подпоследовательность).
- «Можешь ли достичь / возможно ли» попасть в цель (сумма подмножества, разбиение на слова).
…и задача имеет маленькое состояние: каждая подзадача описывается несколькими числами (индекс, оставшаяся вместимость), так число различных подзадач достаточно мало чтобы хранить. Маленькое состояние + перекрывающиеся подзадачи = ДП.
Наивный рекурсивный Фибоначчи
Это учебниковая рекурсия. Она корректна, но она пересчитывает те же подзадачи — цена игнорирования перекрытия.
function fib(n) { // Базовые случаи: fib(0) = 0, fib(1) = 1 if (n <= 1) { return n; } // Рекурсивный случай: две ветки, каждая заново решает перекрывающиеся подзадачи return fib(n - 1) + fib(n - 2); } - L2 Базовые случаи останавливают рекурсию: fib(0)=0 и fib(1)=1.
- L7 Два рекурсивных вызова. fib(n-1) и fib(n-2) оба пересчитывают fib(n-2), fib(n-3), ... — это перекрытие.
Наблюдая как работа взрывается
Добавь счётчик который увеличивается на каждом вызове, потом запусти fib для нескольких размеров. Число вызовов это ровно 2·fib(n+1) − 1, что растёт экспоненциально. Заметь как счётчик скачет дико хотя ответ растёт плавно.
Ответ fib(30) это всего 832040, но потребовалось 2 692 537 вызовов чтобы туда добраться. Добавь 10 к n и число вызовов умножается больше чем на 100. Это экспоненциальный взрыв который вызывают перекрывающиеся подзадачи. (Урок 02 сохраняет каждый ответ один раз и снижает fib(30) до примерно 30 различных вычислений.)
Давай протрассируем левую сторону дерева fib(5) и понаблюдаем как те же подзадачи появляются снова. Каждый кадр показывает какую подзадачу рекурсия сейчас запрашивает, и видели ли мы её раньше.
function fib(n) { if (n <= 1) return n; return fib(n - 1) + fib(n - 2); } Наивная рекурсия: O(2^n) время (точнее O(φ^n))
Каждый вызов fib(n) делает ещё два вызова, так дерево рекурсии ветвится надвое почти в каждом узле. Число вызовов чтобы вычислить fib(n) это ровно 2·fib(n+1) − 1. Поскольку fib(n) сам растёт как φ^n (φ ≈ 1.618, золотое сечение), число вызовов растёт как O(φ^n) ≈ O(1.618^n), что экспоненциально. Люди часто округляют это вверх до O(2^n) потому что дерево почти полное бинарное дерево глубины n. В любом случае: каждый дополнительный +1 к n примерно умножает работу.
Память для наивной рекурсии это O(n): стек вызовов уходит вглубь только настолько насколько длинна самая длинная цепочка (fib(n) → fib(n-1) → … → fib(0)), хотя общее число вызовов экспоненциально.
n naive calls (2*fib(n+1)-1)
5 15
10 177
20 21891
30 2692537 <- 2.7 million calls for a 6-digit answerДинамическое программирование: O(n) время
Есть только n+1 различных подзадач: fib(0) через fib(n). ДП вычисляет каждую ровно раз и сохраняет её, так общая работа это O(n) время. Память это O(n) чтобы держать n+1 сохранённых ответов (урок 03 показывает как сжать это до O(1) храня только последние два значения).
time space
naive O(2^n) O(n) stack
DP O(n) O(n) (down to O(1) possible)Преобразование из O(2^n) в O(n) это вся выгода ДП. Ты тратишь немного памяти чтобы запомнить ответы, и экспоненциальная работа схлопывается в линейную. Вот почему люди говорят что ДП «превращает экспоненциальное в полиномиальное».
Какие два свойства задача должна иметь чтобы динамическое программирование применялось?
Почему наивный рекурсивный Фибоначчи медленный?
Какая ключевая разница между динамическим программированием и «разделяй и властвуй»?
Чем динамическое программирование отличается от жадного алгоритма?
Какая формулировка задачи это сильный сигнал что динамическое программирование может применяться?
Есть только n+1 различных подзадач Фибоначчи (fib(0) через fib(n)). Сколько различных подзадач для fib(10)?
▸Почему это работает
Почему сохранять ответы вместо хитрости с математикой? Есть замкнутая формула для Фибоначчи, но большинство задач ДП не имеют формулы. ДП общее: любая задача с перекрывающимися подзадачами и оптимальной подструктурой может быть ускорена запоминанием ответов, даже когда нет аккуратного уравнения. Приём, не формула, это то что переносится на размен монет, расстояние редактирования, рюкзак и наибольшую общую подпоследовательность.
▸Частая ошибка
Ошибка: думать что каждая рекурсивная задача это задача ДП. ДП помогает только когда подзадачи перекрываются. Сортировка слиянием рекурсивна но её половины непересекающиеся, так кэширование не экономит ничего — это «разделяй и властвуй», не ДП. Прежде чем тянуться за ДП, проверь: решает ли наивная рекурсия ту же подзадачу более одного раза? Если нет, ДП добавляет стоимость памяти без ускорения.
▸Граничные случаи
Когда оптимальная подструктура не выполняется. ДП нужно чтобы лучший ответ целого был построим из лучших ответов подзадач. Самый длинный простой путь в общем графе ломает это: лучший путь через вершину не составлен из лучших путей к его частям, потому что переиспользование вершины запрещено и куски могут конфликтовать. Когда оптимальная подструктура не держится, ДП даёт неверные ответы — перекрытия одного недостаточно.
▸Ещё практика
Тренировка распознавания. Для каждой задачи задай три вопроса: (1) Повторяет ли наивная рекурсия подзадачи? (2) Строится ли лучшее целое из лучших частей? (3) Маленькое ли состояние (несколько чисел)? Если все три да, это ДП. Попробуй на: числе путей в сетке (да), минимуме монет на сумму (да), и сортировке списка (нет — нет перекрытия). Следующие уроки превращают распознанную задачу ДП в работающий код двумя способами: мемоизация (02) и табуляция (03).
Объясни что это динамическое программирование, два свойства которые задача должна иметь чтобы оно применялось, и чем ДП отличается от «разделяй и властвуй» и от жадного.
Динамическое программирование (ДП) решает задачу комбинируя ответы на её подзадачи, вычисляя каждую подзадачу один раз и сохраняя результат чтобы переиспользовать. Реши один раз, запомни, переиспользуй.
Два обязательных свойства:
- Перекрывающиеся подзадачи: наивная рекурсия перерешает ту же подзадачу много раз (fib(3), fib(2) у Фибоначчи появляются снова и снова). Это то что кэширование исправляет.
- Оптимальная подструктура: оптимальный ответ целого строится из оптимальных ответов на подзадачи.
Выгода Фибоначчи: наивная рекурсия это O(2^n) (точнее O(φ^n)) потому что дерево вызовов ветвится надвое и повторяет работу — 2.7 миллиона вызовов для fib(30). Есть только n+1 различных подзадач, так ДП вычисляет каждую раз за O(n) время.
ДП против «разделяй и властвуй»: подзадачи «разделяй и властвуй» непересекающиеся (сортировка слиянием) — нечего кэшировать. Подзадачи ДП перекрываются — кэширование это то что делает его быстрым.
ДП против жадного: жадный фиксирует один локальный выбор и никогда не оглядывается назад; ДП взвешивает все комбинации ответов подзадач и хранит лучший.
Распознавание ДП: «сосчитай способы», «мин/макс по выборам», «можешь ли достичь» — плюс маленькое состояние описывающее каждую подзадачу.
Дальше: урок 02 реализует ДП сверху-вниз с мемоизацией (рекурсия + кэш), а урок 03 реализует его снизу-вверх с табуляцией (заполни таблицу циклом).
Теперь, когда встретишь задачу, наивная рекурсия которой снова и снова решает одну подзадачу, — это твой сигнал: проверь два свойства, назови состояние, тянись за ДП прежде чем писать очередной экспоненциальный перебор.
Практика
Начни сверху. Задачи идут от простого к сложному: вспомнить факт, применить к случаю, затем senior-уровень. Открой, попробуй, потом открой ответ.
Что-то непонятно?
Задай вопрос по этому уроку. Вопросы анонимны и попадают напрямую автору — урок станет лучше.