# Шелдон из Algo Monster: «Освойте паттерны динамического программирования вместо зубрежки»

Источник: https://www.youtube.com/watch?v=66hDgWottdA
Канал: freeCodeCamp.org
Опубликовано: 21.01.2026

---

Динамическое программирование (ДП) часто считается одной из самых сложных тем при подготовке к техническим интервью, однако эксперты утверждают, что ключ к успеху кроется не в зазубривании сотен задач, а в освоении нескольких фундаментальных паттернов. Шелдон, бывший сотрудник Google с десятилетним стажем и наставник платформы Algo Monster, в детальном курсе разбирает, как превратить абстрактную логику оптимизации в понятные визуальные модели.

## 🪜 Основы: Задача о лестнице и магия рекурсии
[[JUMP:01:03]]

Путь к пониманию ДП начинается с классической задачи о лестнице: нужно определить количество способов добраться до $n$-й ступеньки, если за один раз можно сделать шаг на одну или две ступени [01:17]. На примере трех ступенек Шелдон показывает, что существует три пути: три одиночных шага, шаг плюс прыжок, или прыжок плюс шаг [01:30]. Однако с ростом числа ступеней (например, до десяти) ручной подсчет становится невозможным.

Логика решения строится на принципе расширения существующих путей:

*   На первую ступень ведет только 1 путь [01:57].
*   На вторую ступень можно попасть либо двумя шагами по одному, либо одним прыжком на две (итого 2 пути) [02:09].
*   На третью ступень можно попасть только со второй (сделав 1 шаг) или с первой (сделав прыжок на 2 ступени) [02:21].

Следовательно, количество способов достичь ступени $n$ — это сумма способов для ступеней $(n-1)$ и $(n-2)$ [04:07]. Это правило реализуется через рекурсию, где функция вызывает саму себя для подзадач. Однако Шелдон предупреждает: чистая рекурсия крайне неэффективна. Для $n=40$ вычисления займут очень много времени из-за гигантского дерева рекурсии, где одни и те же значения (например, для 3-й ступени) пересчитываются тысячи раз [06:45]. Временная сложность такого алгоритма составляет $O(2^n)$, что при $n=30$ дает около миллиарда лишних операций [07:11].

## 🧠 Мемоизация против Табуляции
[[JUMP:07:36]]

Для решения проблемы избыточных вычислений Шелдон предлагает использовать мемоизацию — технику сохранения результатов в кэше (обычно это хэш-таблица или массив) [08:03]. 

Процесс оптимизации выглядит так:

1.  Перед вычислением проверяем, есть ли результат в хэш-таблице [08:16].
2.  Если есть — возвращаем его мгновенно.
3.  Если нет — вычисляем, сохраняем и только потом возвращаем [10:25].

Мемоизация превращает экспоненциальную сложность в линейную $O(n)$, так как каждый шаг вычисляется ровно один раз [11:17]. Шелдон называет этот подход «рекурсией с памятью» или нисходящим проектированием (top-down) [10:52].

Альтернативный метод — табуляция (bottom-up). Вместо рекурсии используется цикл, который последовательно заполняет массив от базовых случаев к финалу [13:37]. 
Шелдон сравнивает эти подходы:

*   **Мемоизация (Top-down):** Удобна, когда порядок вычислений неочевиден (например, при разделении строк), но требует памяти под стек вызовов и кэш [14:53].
*   **Табуляция (Bottom-up):** Исключает риск переполнения стека и часто более эффективна по памяти [15:19].

## 💰 Паттерн «Постоянный переход»: Минимизация затрат
[[JUMP:20:22]]

Усложнение задачи: теперь каждая ступенька имеет свою стоимость (массив `cost`). Задача — достичь верха лестницы с минимальными затратами [20:35]. Шелдон объясняет, что логика перехода остается прежней: попасть на ступень $n$ можно только с $(n-1)$ или $(n-2)$. Разница лишь в том, что мы выбираем не сумму способов, а `min()` от стоимостей предыдущих шагов, прибавляя стоимость текущей ступени [24:17].

Шелдон выделяет признаки паттерна «Постоянный переход»:

*   Текущее состояние зависит от фиксированного числа предыдущих состояний (в данном случае от двух) [29:56].
*   Формула перехода неизменна для любого этапа [29:56].
*   Возможна оптимизация памяти: если нам нужны только два предыдущих значения, нет смысла хранить весь массив [30:08]. Используя всего две переменные вместо массива, мы снижаем пространственную сложность с $O(n)$ до $O(1)$ [29:30].

Этот же паттерн применяется в задаче «House Robber» (Грабитель домов), где нельзя грабить два соседних дома [30:46]. Формула выбора: либо мы грабим текущий дом и прибавляем добычу к сумме через один дом назад, либо пропускаем текущий и берем максимум для предыдущего дома [32:16].

## 🗺️ Двумерное ДП: Сетки и пути
[[JUMP:33:48]]

Когда движение возможно в нескольких направлениях (например, в сетке $M \times N$), Шелдон вводит понятие двумерного динамического программирования. В задаче «Unique Paths» робот движется из верхнего левого угла в нижний правый, имея право ходить только вправо или вниз [34:30].

Основные правила для сеток по мнению Шелдона:

1.  **Базовые случаи:** Для всех ячеек первой строки и первого столбца существует только 1 путь (движение только в одном направлении вдоль края) [37:06].
2.  **Формула перехода:** Количество путей в ячейку $(i, j)$ равно сумме путей из ячейки сверху и ячейки слева [37:46].
3.  **Оптимизация:** Для вычислений достаточно хранить только одну строку (текущую), обновляя её значения на основе предыдущих [41:04]. Пространственная сложность сокращается до $O(min(M, N))$ [41:31].

Если на сетке появляются препятствия, в ячейки с ними просто записывается 0, так как путей через них не существует [43:28].

## 🧵 Две последовательности: Сравнение строк
[[JUMP:45:25]]

Паттерн «Две последовательности» используется для сравнения двух строк или массивов. Классический пример — поиск самой длинной общей подпоследовательности (LCS) [45:51]. Подпоследовательность отличается от подстроки тем, что символы не обязательно должны идти подряд, но их порядок должен сохраняться [46:03].

Шелдон описывает построение таблицы, где строки — это символы первого слова, а столбцы — второго [49:59]:

*   Если символы совпадают: берем значение из диагональной ячейки (где обе строки были короче на один символ) и прибавляем 1 [51:53].
*   Если не совпадают: берем максимум из верхней или левой ячейки (лучший результат без одного из текущих символов) [52:57].

Этот же принцип применим к задаче об «Расстоянии редактирования» (Edit Distance), где нужно найти минимальное количество вставок, удалений или замен для превращения одного слова в другое [57:56].

## 🔄 Интервальное ДП и палиндромы
[[JUMP:1:01:36]]

Интервальное ДП применяется, когда результат для большого отрезка данных зависит от результатов его внутренних частей [1:11:06]. В задаче о самой длинной палиндромной подпоследовательности Шелдон использует логику краев:

*   Если крайние символы интервала $[i, j]$ совпадают, то длина палиндрома — это 2 плюс длина палиндрома для внутреннего интервала $[i+1, j-1]$ [1:06:19].
*   Если не совпадают — берем максимум от удаления либо левого, либо правого символа [1:07:11].

Главная особенность здесь — порядок заполнения таблицы. Мы идем не по строкам, а по длине интервала: сначала считаем все отрезки длиной 1, затем 2, и так далее [1:07:38].

## 📈 Непостоянный переход: LIS и разделение массива
[[JUMP:1:15:00]]

В некоторых задачах текущее состояние зависит не от фиксированного числа соседей, а от всех предыдущих элементов. Яркий пример — поиск самой длинной возрастающей подпоследовательности (LIS) [1:15:00].
Для каждого элемента массива нам приходится сканировать *все* элементы слева от него [1:19:22]. Если текущий элемент больше какого-то предыдущего, мы можем расширить ту подпоследовательность. Шелдон отмечает, что из-за вложенного цикла временная сложность здесь составляет $O(n^2)$, а оптимизация памяти обычно невозможна, так как нам нужны все прошлые данные [1:22:37].

## 🎒 Задачи типа «Кнапсак» (Рюкзак)
[[JUMP:1:27:10]]

Последний разобранный паттерн касается возможности набора определенной суммы из чисел массива [1:27:10]. В задаче о разделении множества на две равные части (Subset Sum) мы создаем массив булевых значений, где индекс — это возможная сумма [1:31:40].

Критически важный технический нюанс от Шелдона: при обновлении массива сумм нужно двигаться **справа налево** (от больших сумм к меньшим) [1:35:16]. Это гарантирует, что каждое число из исходного набора будет использовано только один раз. Если двигаться слева направо, мы рискуем прибавить одно и то же число к сумме несколько раз, что допустимо только в задачах с неограниченным количеством предметов (например, Coin Change) [1:38:07].