Алгоритмы с нуля
Что это динамическое программирование?
Ты уже знаешь рекурсию: функция вызывает себя на меньшем входе и доверяет что ответ вернётся. Но посмотри что происходит с Фибоначчи. Чтобы получить 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ДП против «разделяй и властвуй»
Оба разбивают задачу на подзадачи. Разница в том, перекрываются ли подзадачи.
- Разделяй и властвуй (сортировка слиянием, бинарный поиск): подзадачи непересекающиеся. Сортировка слиянием разбивает массив на две половины которые не разделяют элементов. Ничего не пересчитывается, так нечего кэшировать — простая рекурсия уже эффективна.
- Динамическое программирование: подзадачи перекрываются. Та же подзадача появляется снова в разных ветвях, так кэширование её ответа это то что делает ДП быстрым.
Правило большого пальца: если кэширование ответов подзадач сэкономило бы работу, это ДП; если каждая подзадача уникальна, это «разделяй и властвуй».
ДП против жадного
Оба могут решать задачи оптимизации, но они выбирают по-разному.
- Жадный фиксирует единственный лучше всего выглядящий выбор на каждом шаге и никогда не пересматривает. Он быстр, но он находит глобальный оптимум только на задачах где локальные выборы гарантированно безопасны.
- Динамическое программирование рассматривает все способы комбинировать ответы подзадач и хранит лучший. Оно исследует комбинации которые жадный пропускает, так оно решает задачи где никакое единое локальное правило не всегда корректно — ценой большей работы.
Распознавание задачи ДП
Задача часто ДП когда ты видишь:
- «Сосчитай способы» сделать что-то (число путей, число декодирований).
- «Найди мин / макс» по множеству выборов (минимум монет, наибольшая возрастающая подпоследовательность).
- «Можешь ли достичь / возможно ли» попасть в цель (сумма подмножества, разбиение на слова).
…и задача имеет маленькое состояние: каждая подзадача описывается несколькими числами (индекс, оставшаяся вместимость), так число различных подзадач достаточно мало чтобы хранить. Маленькое состояние + перекрывающиеся подзадачи = ДП.
Наивный рекурсивный Фибоначчи
Это учебниковая рекурсия. Она корректна, но она пересчитывает те же подзадачи — цена игнорирования перекрытия.
1
function fib(n) {
2
// Base cases: fib(0) = 0, fib(1) = 1
3
if (n <= 1) {
4
return n;
5
}
6
// Recursive case: two branches, each re-solving overlapping subproblems
7
return fib(n - 1) + fib(n - 2);
8
}
- 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) и понаблюдаем как те же подзадачи появляются снова. Каждый кадр показывает какую подзадачу рекурсия сейчас запрашивает, и видели ли мы её раньше.
1
function fib(n) {
2
if (n <= 1) return n;
3
return fib(n - 1) + fib(n - 2);
4
}
Наивная рекурсия: 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 реализует его снизу-вверх с табуляцией (заполни таблицу циклом).