Динамическое программирование (ДП) часто считается одной из самых сложных тем при подготовке к техническим интервью, однако эксперты утверждают, что ключ к успеху кроется не в зазубривании сотен задач, а в освоении нескольких фундаментальных паттернов. Шелдон, бывший сотрудник Google с десятилетним стажем и наставник платформы Algo Monster, в детальном курсе разбирает, как превратить абстрактную логику оптимизации в понятные визуальные модели.
🪜 Основы: Задача о лестнице и магия рекурсии 1:03
Путь к пониманию ДП начинается с классической задачи о лестнице: нужно определить количество способов добраться до $n$-й ступеньки, если за один раз можно сделать шаг на одну или две ступени . На примере трех ступенек Шелдон показывает, что существует три пути: три одиночных шага, шаг плюс прыжок, или прыжок плюс шаг . Однако с ростом числа ступеней (например, до десяти) ручной подсчет становится невозможным.
Логика решения строится на принципе расширения существующих путей:
- На первую ступень ведет только 1 путь .
- На вторую ступень можно попасть либо двумя шагами по одному, либо одним прыжком на две (итого 2 пути) .
- На третью ступень можно попасть только со второй (сделав 1 шаг) или с первой (сделав прыжок на 2 ступени) .
Следовательно, количество способов достичь ступени $n$ — это сумма способов для ступеней $(n-1)$ и $(n-2)$ . Это правило реализуется через рекурсию, где функция вызывает саму себя для подзадач. Однако Шелдон предупреждает: чистая рекурсия крайне неэффективна. Для $n=40$ вычисления займут очень много времени из-за гигантского дерева рекурсии, где одни и те же значения (например, для 3-й ступени) пересчитываются тысячи раз . Временная сложность такого алгоритма составляет $O(2^n)$, что при $n=30$ дает около миллиарда лишних операций .
🧠 Мемоизация против Табуляции 7:36
Для решения проблемы избыточных вычислений Шелдон предлагает использовать мемоизацию — технику сохранения результатов в кэше (обычно это хэш-таблица или массив) .
Процесс оптимизации выглядит так:
- Перед вычислением проверяем, есть ли результат в хэш-таблице .
- Если есть — возвращаем его мгновенно.
- Если нет — вычисляем, сохраняем и только потом возвращаем .
Мемоизация превращает экспоненциальную сложность в линейную $O(n)$, так как каждый шаг вычисляется ровно один раз . Шелдон называет этот подход «рекурсией с памятью» или нисходящим проектированием (top-down) .
Альтернативный метод — табуляция (bottom-up). Вместо рекурсии используется цикл, который последовательно заполняет массив от базовых случаев к финалу . Шелдон сравнивает эти подходы:
- Мемоизация (Top-down): Удобна, когда порядок вычислений неочевиден (например, при разделении строк), но требует памяти под стек вызовов и кэш .
- Табуляция (Bottom-up): Исключает риск переполнения стека и часто более эффективна по памяти .
💰 Паттерн «Постоянный переход»: Минимизация затрат 20:22
Усложнение задачи: теперь каждая ступенька имеет свою стоимость (массив cost). Задача — достичь верха лестницы с минимальными затратами . Шелдон объясняет, что логика перехода остается прежней: попасть на ступень $n$ можно только с $(n-1)$ или $(n-2)$. Разница лишь в том, что мы выбираем не сумму способов, а min() от стоимостей предыдущих шагов, прибавляя стоимость текущей ступени .
Шелдон выделяет признаки паттерна «Постоянный переход»:
- Текущее состояние зависит от фиксированного числа предыдущих состояний (в данном случае от двух) .
- Формула перехода неизменна для любого этапа .
- Возможна оптимизация памяти: если нам нужны только два предыдущих значения, нет смысла хранить весь массив . Используя всего две переменные вместо массива, мы снижаем пространственную сложность с $O(n)$ до $O(1)$ .
Этот же паттерн применяется в задаче «House Robber» (Грабитель домов), где нельзя грабить два соседних дома . Формула выбора: либо мы грабим текущий дом и прибавляем добычу к сумме через один дом назад, либо пропускаем текущий и берем максимум для предыдущего дома .
🗺️ Двумерное ДП: Сетки и пути 33:48
Когда движение возможно в нескольких направлениях (например, в сетке $M \times N$), Шелдон вводит понятие двумерного динамического программирования. В задаче «Unique Paths» робот движется из верхнего левого угла в нижний правый, имея право ходить только вправо или вниз .
Основные правила для сеток по мнению Шелдона:
- Базовые случаи: Для всех ячеек первой строки и первого столбца существует только 1 путь (движение только в одном направлении вдоль края) .
- Формула перехода: Количество путей в ячейку $(i, j)$ равно сумме путей из ячейки сверху и ячейки слева .
- Оптимизация: Для вычислений достаточно хранить только одну строку (текущую), обновляя её значения на основе предыдущих . Пространственная сложность сокращается до $O(min(M, N))$ .
Если на сетке появляются препятствия, в ячейки с ними просто записывается 0, так как путей через них не существует .
🧵 Две последовательности: Сравнение строк 45:25
Паттерн «Две последовательности» используется для сравнения двух строк или массивов. Классический пример — поиск самой длинной общей подпоследовательности (LCS) . Подпоследовательность отличается от подстроки тем, что символы не обязательно должны идти подряд, но их порядок должен сохраняться .
Шелдон описывает построение таблицы, где строки — это символы первого слова, а столбцы — второго :
- Если символы совпадают: берем значение из диагональной ячейки (где обе строки были короче на один символ) и прибавляем 1 .
- Если не совпадают: берем максимум из верхней или левой ячейки (лучший результат без одного из текущих символов) .
Этот же принцип применим к задаче об «Расстоянии редактирования» (Edit Distance), где нужно найти минимальное количество вставок, удалений или замен для превращения одного слова в другое .
🔄 Интервальное ДП и палиндромы 1:01:36
Интервальное ДП применяется, когда результат для большого отрезка данных зависит от результатов его внутренних частей . В задаче о самой длинной палиндромной подпоследовательности Шелдон использует логику краев:
- Если крайние символы интервала $[i, j]$ совпадают, то длина палиндрома — это 2 плюс длина палиндрома для внутреннего интервала $[i+1, j-1]$ .
- Если не совпадают — берем максимум от удаления либо левого, либо правого символа .
Главная особенность здесь — порядок заполнения таблицы. Мы идем не по строкам, а по длине интервала: сначала считаем все отрезки длиной 1, затем 2, и так далее .
📈 Непостоянный переход: LIS и разделение массива 1:15:00
В некоторых задачах текущее состояние зависит не от фиксированного числа соседей, а от всех предыдущих элементов. Яркий пример — поиск самой длинной возрастающей подпоследовательности (LIS) . Для каждого элемента массива нам приходится сканировать все элементы слева от него . Если текущий элемент больше какого-то предыдущего, мы можем расширить ту подпоследовательность. Шелдон отмечает, что из-за вложенного цикла временная сложность здесь составляет $O(n^2)$, а оптимизация памяти обычно невозможна, так как нам нужны все прошлые данные .
🎒 Задачи типа «Кнапсак» (Рюкзак) 1:27:10
Последний разобранный паттерн касается возможности набора определенной суммы из чисел массива . В задаче о разделении множества на две равные части (Subset Sum) мы создаем массив булевых значений, где индекс — это возможная сумма .
Критически важный технический нюанс от Шелдона: при обновлении массива сумм нужно двигаться справа налево (от больших сумм к меньшим) . Это гарантирует, что каждое число из исходного набора будет использовано только один раз. Если двигаться слева направо, мы рискуем прибавить одно и то же число к сумме несколько раз, что допустимо только в задачах с неограниченным количеством предметов (например, Coin Change) .
