🔴 Сложный ⏱️ 55 минут

Динамическое программирование

📋 Содержание урока

Динамическое программирование 🧩

Представь систему распознавания речи. На вход поступает звуковой сигнал, разбитый на короткие временные отрезки — кадры, а на выходе нужно получить наиболее вероятную последовательность фонем, которая этот сигнал породила. Для каждого кадра модель видит лишь размытое, шумное распределение вероятностей «это похоже на такой-то звук», а скрытая последовательность фонем — это то, что система должна восстановить. Если действовать в лоб и перебрать все возможные последовательности скрытых состояний длиной в несколько сотен кадров, число вариантов взрывается экспоненциально — уже для полусотни кадров и десятка возможных фонем на кадр это больше вариантов, чем атомов в теле человека. И тем не менее подобные системы работают в реальном времени на смартфонах. Секрет в том, что подавляющее большинство этих вариантов можно вообще не считать: лучший путь, заканчивающийся в определённом состоянии на определённом шаге, всегда строится из лучшего пути, заканчивающегося в одном из состояний на предыдущем шаге, — считать его заново для каждого варианта продолжения бессмысленно.

Именно эту идею — заменить перебор экспоненциального числа вариантов вычислением по формуле, которая опирается на уже посчитанные меньшие кусочки задачи, — и называют динамическим программированием (ДП). Это не какой-то один конкретный алгоритм, а общая техника: если задачу можно разбить на подзадачи так, что оптимальное решение всей задачи собирается из оптимальных решений подзадач, а сами подзадачи при этом многократно повторяются в разных ветвях перебора, — экспоненциальный перебор можно превратить в полиномиальный алгоритм, один раз посчитав каждую уникальную подзадачу и переиспользуя готовый ответ везде, где он снова понадобится.

В прошлых уроках ты уже встречал стратегию «разделяй и властвуй» — сортировку слиянием и быструю сортировку, которые тоже разбивают задачу на подзадачи и решают их рекурсивно. Но там подзадачи никогда не повторяются: половины массива при сортировке слиянием — это всегда непересекающиеся, уникальные куски данных, и второй раз сортировать один и тот же подмассив не приходится. Динамическое программирование нужно ровно тогда, когда это условие нарушается — когда дерево рекурсии содержит одни и те же подзадачи снова и снова, и наивная рекурсия начинает пересчитывать уже известные ответы вхолостую.

В этом уроке ты разберёшь два строгих формальных условия, при которых ДП вообще применимо, — оптимальную подструктуру и перекрывающиеся подзадачи, — а затем на примере чисел Фибоначчи увидишь два способа реализовать идею ДП на практике: мемоизацию (рекурсия сверху вниз с кэшем готовых ответов) и табуляцию (итеративное заполнение таблицы снизу вверх). После этого ты разберёшь два классических примера, на которых обучают динамическому программированию по всему миру, — задачу о рюкзаке 0/1 и редакционное расстояние Левенштейна, — причём не только найдёшь оптимальное значение, но и научишься восстанавливать само решение: какие предметы положить в рюкзак, какими именно операциями редактирования одно слово превращается в другое. А в конце урока ты увидишь, как ровно эта же схема лежит в основе алгоритма Витерби — рабочей лошадки распознавания речи, обработки естественного языка и биоинформатики.

История

Термин «динамическое программирование» придумал американский математик Ричард Беллман в начале 1950-х годов, работая в исследовательской корпорации RAND над задачами многоступенчатого принятия решений — теми, где нужно последовательно выбирать действия так, чтобы максимизировать суммарный выигрыш на всём горизонте планирования. Беллман сформулировал ключевое наблюдение, которое сегодня носит его имя — уравнение Беллмана: оптимальное решение многошаговой задачи, начиная с любого текущего состояния, складывается из немедленной выгоды на этом шаге и оптимального решения оставшейся, более короткой задачи. Это и есть, в других словах, принцип оптимальной подструктуры, который ты разберёшь в следующем разделе, — просто сформулированный на полтора десятилетия раньше, чем сложилась современная информатика как дисциплина.

Происхождение самого слова «динамическое» — одна из самых известных историй в истории вычислительной техники, и Беллман рассказал её сам в автобиографии «Глаз урагана». RAND в те годы работала по контрактам с министерством обороны США, а тогдашний министр обороны Чарльз Уилсон был известен своей резкой неприязнью к слову «исследование» (research) — оно ассоциировалось у него с абстрактной, непонятной наукой, на которую не стоит выделять бюджет. Беллману нужно было название для своей математической работы, которое, с одной стороны, звучало бы солидно, а с другой — не вызывало бы недовольства чиновников. Слово «программирование» он выбрал в смысле «планирование, составление расписания» — как в выражении «программа мероприятия», а вовсе не в смысле написания кода для компьютера (компьютерное программирование как профессия тогда только зарождалось). А прилагательное «динамическое» Беллман добавил намеренно ради звучности и потому, что, по его собственным словам, это слово почти невозможно было истолковать в уничижительном смысле — оно ассоциировалось с движением, энергией, прогрессом. Получилось название, которое, как признавался сам Беллман, «было практически защищено от нападок».

Из теории оптимального управления идея довольно быстро перекочевала в вычислительную математику и информатику: уравнение Беллмана легло в основу алгоритма Беллмана — Форда для поиска кратчайших путей в графах с отрицательными весами, а сама идея «заполнить таблицу подзадач один раз и переиспользовать результаты» стала стандартным инструментом в анализе алгоритмов наравне с жадными алгоритмами и «разделяй и властвуй». Сегодня динамическое программирование в том или ином виде встречается почти в любой области, где нужно находить оптимум среди экспоненциально большого числа вариантов, — от биоинформатики и обработки естественного языка до планирования маршрутов и обучения с подкреплением, где уравнение Беллмана используется практически без изменений, только с вероятностями и ожидаемыми наградами вместо детерминированных весов.

Условия применимости: оптимальная подструктура и перекрывающиеся подзадачи

Интуиция

Прежде чем городить рекурсию с кэшем или таблицу под задачу, стоит проверить, применимо ли ДП вообще — потому что попытка «закэшировать» задачу, которая для этого не годится, в лучшем случае не даст ускорения, а в худшем — даст неверный ответ. Представь, что ты собираешь маршрут из точки A в точку Z через промежуточные города, и хочешь найти самый дешёвый билет. Если самый дешёвый маршрут A→Z проходит через город M, то отрезок этого маршрута от A до M обязан сам быть самым дешёвым маршрутом от A до M — иначе можно было бы заменить этот отрезок на более дешёвый и получить маршрут A→Z ещё дешевле, а значит, исходный маршрут не был самым дешёвым. Это и есть оптимальная подструктура: оптимальное решение всей задачи можно собрать из оптимальных решений её подзадач.

Но одной оптимальной подструктуры недостаточно, чтобы динамическое программирование давало выигрыш в скорости — без второго условия это просто рекурсия, которая ничем не отличается от «разделяй и властвуй» из прошлых уроков. Представь теперь, что при переборе вариантов маршрута ты то и дело натыкаешься на одну и ту же промежуточную подзадачу — «какой самый дешёвый путь от M до Z» — снова и снова, приходя в M разными путями. Вот это и есть перекрывающиеся подзадачи: одна и та же меньшая подзадача встречается многократно в разных ветвях полного перебора. Именно это условие оправдывает кэш: если бы каждая подзадача встречалась ровно один раз (как в сортировке слиянием), кэшировать было бы нечего — экономить было бы не на чем.

Алгоритм

Два необходимых условия применимости динамического программирования:

  1. Оптимальная подструктура. Задачу можно разбить на подзадачи так, что оптимальное решение исходной задачи строится из оптимальных решений этих подзадач (обычно — через простую комбинирующую операцию вроде минимума, максимума или суммы над вариантами).
  2. Перекрывающиеся подзадачи. При наивном рекурсивном переборе одни и те же подзадачи (с одинаковыми параметрами) возникают многократно в разных ветвях дерева рекурсии, а не по одному разу, как в классическом «разделяй и властвуй».

Практическая проверка на этапе проектирования решения:

  1. Сформулировать состояние подзадачи — минимальный набор параметров, однозначно её определяющий (например, «наибольшая общая подпоследовательность первых i и первых j символов двух строк»).
  2. Записать рекуррентную формулу: как оптимальный ответ для состояния выражается через ответы для меньших состояний.
  3. Нарисовать (хотя бы мысленно) дерево наивной рекурсии для небольшого входа и проверить, повторяются ли в нём одинаковые вызовы. Если нет — перекрывающихся подзадач нет, ДП не даст ускорения, и достаточно обычной рекурсии «разделяй и властвуй» или жадного алгоритма.

Разбор примеров

Пример 1 (перекрывающиеся подзадачи на числах Фибоначчи). Построить дерево наивной рекурсии для вычисления $\text{fib}(5)$ по формуле $\text{fib}(n) = \text{fib}(n-1) + \text{fib}(n-2)$ и посчитать, сколько раз вызывается каждая подзадача.

Дерево вызовов выглядит так: fib(5) вызывает fib(4) и fib(3); fib(4) в свою очередь вызывает fib(3) и fib(2); а исходный fib(3) (правый потомок fib(5)) вызывает ещё одну пару fib(2) и fib(1). Уже на этом уровне видно: подзадача fib(3) встретилась дважды — один раз как потомок fib(4), второй раз как прямой потомок fib(5), и оба раза она честно пересчитывается заново, со всеми своими собственными потомками. Если продолжить разворачивать дерево до конца, fib(2) встретится трижды, fib(1) — пять раз, fib(0) — трижды. Всего для вычисления fib(5) наивная рекурсия сделает 15 вызовов функции — притом что различных подзадач всего шесть: fib(0), fib(1), fib(2), fib(3), fib(4), fib(5). Число повторных вызовов растёт экспоненциально с ростом $n$ (по формуле $2F(n+1)-1$, где $F$ — сама последовательность Фибоначчи), тогда как число уникальных подзадач растёт линейно — это и есть перекрывающиеся подзадачи в чистом виде.

Пример 2 (оптимальная подструктура на кратчайшем пути). Дан ориентированный граф с вершинами $A, B, C, D$ и рёбрами $A{\to}B$ (вес 2), $A{\to}C$ (вес 5), $B{\to}C$ (вес 1), $B{\to}D$ (вес 6), $C{\to}D$ (вес 2). Найти кратчайший путь из $A$ в $D$ и проверить, обладает ли задача оптимальной подструктурой.

Перебираем простые пути: $A{\to}B{\to}D$ стоит $2+6=8$; $A{\to}C{\to}D$ стоит $5+2=7$; $A{\to}B{\to}C{\to}D$ стоит $2+1+2=5$. Минимальный — третий, длиной 5. Теперь проверим оптимальную подструктуру: подпуть этого маршрута от $A$ до $C$ — это $A{\to}B{\to}C$ стоимостью $2+1=3$. Совпадает ли это с отдельно посчитанным кратчайшим путём от $A$ до $C$? Прямое ребро $A{\to}C$ стоит 5, а путь через $B$ стоит 3 — значит, кратчайший путь от $A$ до $C$ действительно равен 3, и это ровно тот же отрезок, что участвует в кратчайшем пути от $A$ до $D$. Оптимальная подструктура подтверждается: кратчайший путь к конечной точке проходит только через кратчайшие пути к промежуточным точкам, и именно на этом факте построены изученные в прошлых уроках алгоритмы Дейкстры и Флойда — Уоршелла.

Пример 3 (контрпример — отсутствие оптимальной подструктуры). Дан неориентированный граф-«квадрат» с вершинами $A, B, C, D$, рёбрами $A{-}B$, $B{-}C$, $C{-}D$, $D{-}A$ и дополнительной диагональю $B{-}D$. Найти самый длинный простой путь (без повторения вершин) от $A$ до $C$ и проверить, можно ли его собрать из самого длинного простого пути от $A$ до какой-либо промежуточной вершины.

Перебираем простые пути от $A$ до $C$: $A{-}B{-}C$ (2 ребра), $A{-}D{-}C$ (2 ребра), $A{-}B{-}D{-}C$ (3 ребра), $A{-}D{-}B{-}C$ (3 ребра). Самый длинный — 3 ребра, например $A{-}B{-}D{-}C$. Теперь посмотрим на его начальный отрезок $A{-}B{-}D$: это путь от $A$ до $D$ длиной 2 ребра. Но самый длинный простой путь от $A$ до $D$ сам по себе — это $A{-}B{-}C{-}D$, длиной 3 ребра! Он длиннее, чем отрезок $A{-}B{-}D$, использованный внутри оптимального пути до $C$. Однако взять именно этот, более длинный путь до $D$ как «строительный блок» нельзя: он уже использует вершину $C$, а значит, дойти из него до $C$ второй раз, не повторив вершину, невозможно. Локально оптимальный (самый длинный) подпуть до промежуточной точки оказывается бесполезен для построения глобально оптимального решения — он «съедает» ресурс (непосещённые вершины), нужный дальше. Это и есть отсутствие оптимальной подструктуры: для задачи о самом длинном простом пути динамическое программирование в его обычном виде не работает, и не случайно эта задача относится к NP-трудным.

Почему это важно

Проверка этих двух условий — не формальность для учебника, а конкретный фильтр, экономящий время на реальном проекте. Если кто-то предлагает «закэшировать» рекурсивную функцию, у которой каждая подзадача при переборе встречается ровно один раз, — мемоизация не ускорит код, а лишь добавит накладные расходы на работу с хэш-таблицей. И наоборот: если задача внешне похожа на оптимизационную, но не обладает оптимальной подструктурой (как самый длинный простой путь в примере 3, или задача коммивояжёра в её точной формулировке), попытка «на автомате» написать ДП даст либо неверный ответ, либо экспоненциальную по времени программу, которая просто переберёт все состояния без реальной экономии, — и в таких случаях нужны другие инструменты: точные переборные алгоритмы с отсечениями (тема одного из следующих уроков — backtracking) или приближённые эвристики.

Мемоизация «сверху вниз» и табуляция «снизу вверх»: числа Фибоначчи

Интуиция

Когда оба условия применимости подтверждены, остаётся выбрать, как именно избавиться от повторных вычислений. Есть два зеркальных подхода. Мемоизация оставляет рекурсию как она есть — задача по-прежнему решается «сверху» (от большого $n$ к маленькому), — но перед каждым вычислением функция сначала заглядывает в кэш: если ответ для этих параметров уже когда-то считался, он просто возвращается оттуда, без повторного спуска в рекурсию. Табуляция, наоборот, отказывается от рекурсии вовсе и заполняет таблицу ответов «снизу» — от самых маленьких, тривиальных подзадач к исходной, — при этом каждая ячейка таблицы вычисляется ровно один раз, обычным циклом, а не вызовом функции.

На примере чисел Фибоначчи разница видна особенно ясно, потому что задача предельно простая, а сравнение подходов — предельно наглядное: без кэша число операций растёт экспоненциально, с кэшем — линейно, независимо от того, идёшь ли ты «сверху вниз» с мемоизацией или «снизу вверх» табуляцией.

Алгоритм

Мемоизация (сверху вниз, memoization):

  1. Завести словарь cache для хранения уже посчитанных ответов.
  2. При вызове fib(n) сначала проверить, есть ли n в cache — если да, немедленно вернуть сохранённое значение без дальнейших вычислений.
  3. Если n в cache нет: если n <= 1, вернуть n (база рекурсии); иначе рекурсивно вычислить fib(n-1) + fib(n-2).
  4. Перед возвратом результата сохранить его в cache[n], чтобы повторный вызов с тем же n (в любой другой ветви рекурсии) обошёлся без пересчёта.

Табуляция (снизу вверх, tabulation):

  1. Завести массив (или просто две переменные) для хранения значений fib(0), fib(1), ..., fib(n).
  2. Заполнить базовые случаи: dp[0] = 0, dp[1] = 1.
  3. Циклом от i = 2 до n вычислять dp[i] = dp[i-1] + dp[i-2], используя уже заполненные, более ранние ячейки таблицы.
  4. Вернуть dp[n] — никакой рекурсии, только линейный проход по уже готовым значениям.
import functools

# Мемоизация: рекурсия + кэш
@functools.lru_cache(maxsize=None)
def fib_memo(n):
    if n <= 1:
        return n
    return fib_memo(n - 1) + fib_memo(n - 2)


# Табуляция: итеративное заполнение таблицы
def fib_tab(n):
    if n <= 1:
        return n
    dp = [0] * (n + 1)
    dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]


# Табуляция с O(1) памяти: храним только последние два значения
def fib_tab_optimized(n):
    if n <= 1:
        return n
    prev2, prev1 = 0, 1
    for _ in range(2, n + 1):
        prev2, prev1 = prev1, prev2 + prev1
    return prev1

Разбор примеров

Пример 1 (взрыв без кэша). Оценить число вызовов функции для наивной рекурсии fib(30) и fib(50) без какого-либо кэша, используя формулу $\text{calls}(n) = 2F(n+1) - 1$.

Для $n=30$: $F(31) = 1\,346\,269$, значит $\text{calls}(30) = 2 \cdot 1\,346\,269 - 1 = 2\,692\,537$ — уже почти три миллиона вызовов функции ради одного числа, но современный процессор с этим ещё справляется за доли секунды. Для $n=50$: $F(51) = 20\,365\,011\,074$, значит $\text{calls}(50) \approx 4{,}07 \times 10^{10}$ — свыше сорока миллиардов вызовов. При скорости порядка сотен миллионов простых вызовов в секунду это уже десятки секунд или минуты одного вычисления, а fib(90) таким способом станет практически невычислимым на любом железе. При этом табуляция находит fib(90) за 90 шагов цикла мгновенно. Это и есть разница между экспоненциальной и линейной сложностью, доведённая до конкретных чисел.

Пример 2 (трассировка мемоизации). Проследить порядок заполнения кэша при вызове fib_memo(6).

Вызов fib(6) не находит 6 в кэше и спускается к fib(5) + fib(4). fib(5) не находит 5 в кэше и спускается к fib(4) + fib(3). fib(4) не находит 4 и спускается к fib(3) + fib(2). fib(3) спускается к fib(2) + fib(1). fib(2) спускается к fib(1) + fib(0) — оба базовые случаи, возвращают 1 и 0 без обращения к кэшу (значения 0 и 1 для аргументов 0 и 1 в реализации не кэшируются отдельно, так как база рекурсии не выполняет рекурсивных вызовов). fib(2) вычисляет 1 + 0 = 1, сохраняет cache[2] = 1 и возвращает 1 наверх. Теперь fib(3) может вычислить fib(1) — это снова базовый случай, 1 — и получает 1 + 1 = 2, сохраняет cache[3] = 2. fib(4) вычисляет уже сохранённое fib(3) через кэш вместо нового вызова со всем поддеревом, fib(4) = 2 + fib(2), а fib(2) тоже берётся напрямую из кэша (= 1), давая fib(4) = 3, сохраняет cache[4] = 3. Возвращаясь к fib(5) = fib(4) + fib(3), обе величины уже в кэше — 3 и 2, значит fib(5) = 5 без единого нового рекурсивного вызова, сохраняет cache[5] = 5. Наконец fib(6) = fib(5) + fib(4) = 5 + 3 = 8, оба слагаемых берутся из кэша мгновенно. Порядок заполнения кэша: cache[2]=1 → cache[3]=2 → cache[4]=3 → cache[5]=5 → cache[6]=8. Обрати внимание: несмотря на то что рекурсивная структура вызовов формально та же, что и в наивной версии, каждое значение вычисляется ровно один раз — второй раз оно просто читается из словаря.

Пример 3 (трассировка табуляции). Заполнить таблицу для fib_tab(10) и показать переход к варианту с $O(1)$ памяти.

$i$ 0 1 2 3 4 5 6 7 8 9 10
dp[i] 0 1 1 2 3 5 8 13 21 34 55

Каждая ячейка получается сложением двух предыдущих: $dp[2]=dp[1]+dp[0]=1+0=1$, $dp[3]=dp[2]+dp[1]=1+1=2$, и так далее вплоть до $dp[10]=dp[9]+dp[8]=34+21=55$. Никакой рекурсии, никакого стека вызовов — просто линейный проход слева направо. При этом видно, что для вычисления dp[i] реально нужны только два последних значения, dp[i-1] и dp[i-2], — всё, что старше, уже не понадобится. Именно поэтому версию fib_tab_optimized можно свести к двум переменным prev2, prev1, которые на каждом шаге сдвигаются вправо: память падает с $O(n)$ до $O(1)$, а время остаётся $O(n)$.

Почему это важно

Мемоизация и табуляция не взаимозаменяемы в реальных задачах — у каждой есть своя ниша. Мемоизация особенно выгодна, когда из всего теоретически возможного пространства подзадач реально используется лишь небольшая, заранее непредсказуемая часть — например, в рекурсии с дополнительными ограничениями или отсечениями, где заранее неясно, какие именно состояния вообще будут достигнуты: тогда кэш считает только то, что реально понадобилось, а полная таблица заполнила бы кучу ячеек впустую. Табуляция, наоборот, выигрывает, когда нужны все ответы вплоть до целевого (как для fib, где fib(n) в любом случае требует прохода через все меньшие значения), — она не тратит время на накладные расходы рекурсивных вызовов и работу с хэш-таблицей, а вдобавок открывает прямой путь к оптимизации памяти через «скользящее окно» по таблице, как в примере 3. Есть и практическое инженерное соображение: рекурсия в большинстве языков ограничена глубиной стека вызовов, и мемоизированная реализация fib(100000) упадёт с переполнением стека там, где итеративная табуляция отработает без проблем.

Задача о рюкзаке 0/1: полный разбор таблицы

Интуиция

Классическая задача: у тебя есть рюкзак с ограниченной грузоподъёмностью и набор предметов, у каждого — свой вес и своя ценность. Нужно выбрать подмножество предметов, максимизирующее суммарную ценность так, чтобы суммарный вес не превысил вместимость рюкзака. Ключевое слово «0/1» означает, что каждый предмет либо кладётся в рюкзак целиком, либо не кладётся вовсе — дробить предметы нельзя, в отличие от «непрерывной» версии задачи, где допустимы доли (например, зерно или жидкость можно отсыпать частично). Это ограничение принципиально меняет и структуру решения, и его сложность, как ты увидишь в примере 2.

Задача обладает и перекрывающимися подзадачами, и оптимальной подструктурой: состояние подзадачи — «какова максимальная ценность, которую можно набрать, рассматривая только первые $i$ предметов и располагая вместимостью $w$» — и это состояние действительно многократно переиспользуется при разных комбинациях выбора предыдущих предметов, а оптимальное решение для полного набора предметов строится из оптимальных решений для меньших наборов.

Алгоритм

Рекуррентная формула 0/1 рюкзака. Пусть $dp[i][w]$ — максимальная ценность, которую можно набрать, используя только первые $i$ предметов, при ограничении по весу $w$. Для $i$-го предмета с весом $\text{wt}_i$ и ценностью $\text{val}_i$:

$$dp[i][w] = \begin{cases} dp[i-1][w], & \text{если } \text{wt}_i > w \text{ (предмет не влезает)} \\ \max\big(dp[i-1][w],\; dp[i-1][w - \text{wt}_i] + \text{val}_i\big), & \text{иначе} \end{cases}$$

Базовые случаи: $dp[0][w] = 0$ для любого $w$ (без предметов ценность нулевая) и $dp[i][0] = 0$ для любого $i$ (без вместимости ничего не унести). Ответ на всю задачу — $dp[n][W]$, где $n$ — число предметов, $W$ — вместимость рюкзака.

def knapsack_01(weights, values, capacity):
    n = len(weights)
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        for w in range(capacity + 1):
            if weights[i - 1] > w:
                dp[i][w] = dp[i - 1][w]
            else:
                dp[i][w] = max(
                    dp[i - 1][w],
                    dp[i - 1][w - weights[i - 1]] + values[i - 1]
                )

    return dp[n][capacity]

Разбор примеров

Пример 1 (полная трассировка таблицы). Четыре предмета: вес/ценность $(2,3)$, $(3,4)$, $(4,5)$, $(5,6)$, вместимость рюкзака $W=5$. Заполнить таблицу целиком.

$i \backslash w$ 0 1 2 3 4 5
0 (нет предметов) 0 0 0 0 0 0
1: $(2,3)$ 0 0 3 3 3 3
2: $(3,4)$ 0 0 3 4 4 7
3: $(4,5)$ 0 0 3 4 5 7
4: $(5,6)$ 0 0 3 4 5 7

Разбор строки 1 (только предмет весом 2, ценностью 3): при $w<2$ предмет не влезает, ячейка наследует 0 сверху; при $w \geq 2$ можно взять предмет, ценность становится 3. Разбор строки 2 (добавили предмет весом 3, ценностью 4): при $w=3$ сравниваем «не брать» ($dp[1][3]=3$) и «взять» ($dp[1][0]+4=0+4=4$) — берём максимум 4; при $w=5$ сравниваем «не брать» ($dp[1][5]=3$) и «взять» ($dp[1][2]+4=3+4=7$) — максимум 7, оба предмета помещаются одновременно (вес $2+3=5$). Строки 3 и 4 не улучшают результат при $w=5$: для предмета 3 сравнение даёт $\max(dp[2][5]=7,\ dp[2][1]+5=0+5=5)=7$, для предмета 4 — $\max(dp[3][5]=7,\ dp[3][0]+6=0+6=6)=7$. Итог: $dp[4][5]=7$, достигается на предметах 1 и 2 (суммарный вес $2+3=5$, суммарная ценность $3+4=7$).

Пример 2 (почему жадный алгоритм не работает для 0/1, в отличие от непрерывной версии). Три предмета: вес/ценность $(10, 60)$, $(20, 100)$, $(30, 120)$, вместимость $W=50$. Сравнить результат жадного алгоритма по убыванию удельной ценности $\text{val}/\text{wt}$ с настоящим оптимумом.

Удельные ценности: предмет 1 — $60/10=6$, предмет 2 — $100/20=5$, предмет 3 — $120/30=4$. Жадный алгоритм в 0/1-постановке берёт по убыванию удельной ценности до тех пор, пока предмет влезает целиком: сначала предмет 1 (вес 10, остаток вместимости 40), затем предмет 2 (вес 20, остаток вместимости 20) — итого вес $30$, ценность $60+100=160$; предмет 3 весом 30 уже не влезает в оставшиеся 20 единиц вместимости, и жадный алгоритм на этом останавливается с результатом 160. Но переберём все допустимые по весу подмножества напрямую: $\{1,3\}$ — вес $10+30=40 \leq 50$, ценность $60+120=180$; $\{2,3\}$ — вес $20+30=50 \leq 50$, ценность $100+120=\mathbf{220}$; $\{1,2,3\}$ — вес $60 > 50$, недопустимо. Настоящий оптимум — 220 на подмножестве $\{2,3\}$, что заметно больше жадных 160. Жадный выбор «сначала самое выгодное по отношению вес/ценность» подводит именно потому, что в 0/1-версии нельзя добрать рюкзак остатком дробного предмета — а в непрерывной задаче (где предметы можно резать на доли) тот же самый жадный алгоритм, наоборот, доказуемо оптимален, потому что недостающий кусок вместимости всегда можно закрыть долей следующего по выгодности предмета.

Пример 3 (восстановление выбранных предметов). Используя таблицу из примера 1, восстановить набор предметов, обеспечивающих $dp[4][5]=7$, обратным проходом по таблице.

Начинаем с $dp[4][5]=7$. Сравниваем со значением строкой выше: $dp[3][5]=7$ — совпадает, значит предмет 4 не был взят (иначе значение отличалось бы), переходим к $dp[3][5]$. Сравниваем $dp[3][5]=7$ с $dp[2][5]=7$ — снова совпадает, предмет 3 не взят, переходим к $dp[2][5]$. Сравниваем $dp[2][5]=7$ с $dp[1][5]=3$ — значения разные, значит предмет 2 (вес 3, ценность 4) взят: вычитаем его вес из вместимости, $5-3=2$, и переходим к $dp[1][2]$. Сравниваем $dp[1][2]=3$ с $dp[0][2]=0$ — значения разные, значит предмет 1 (вес 2, ценность 3) тоже взят: вычитаем вес, $2-2=0$, переходим к $dp[0][0]=0$ — вместимость и число рассмотренных предметов одновременно обнулились, обратный проход завершён. Восстановленный набор: предметы 1 и 2, суммарный вес $2+3=5$, суммарная ценность $3+4=7$ — в точности совпадает с ответом из примера 1, но теперь известно не только число 7, а конкретно, что́ нужно положить в рюкзак.

Почему это важно

Задача о рюкзаке — не абстрактное упражнение, а прямая модель распределения ограниченного бюджета: выбор набора признаков при ограничении на объём вычислений или память модели, выбор подмножества экспериментов при ограниченном бюджете на A/B-тестирование, отбор задач в спринт при ограниченном времени команды — во всех этих случаях речь идёт о том же самом «максимизировать суммарную ценность при ограничении на суммарный ресурс». А урок про восстановление решения не менее важен на практике, чем сама оптимизация: заказчику или пользователю почти никогда не нужно голое число «максимальная ценность — 7» — нужен конкретный список, что́ выбрать, и именно обратный проход по таблице даёт этот список без дополнительного перебора.

Редакционное расстояние Левенштейна и восстановление решения

Интуиция

Редакционное расстояние Левенштейна — это минимальное число односимвольных операций (вставка символа, удаление символа, замена символа на другой), которое превращает одну строку в другую. Интуитивно это мера «непохожести» двух строк: чем меньше расстояние, тем более родственны слова. Задача обладает перекрывающимися подзадачами и оптимальной подструктурой ровно тем же способом, что и все алгоритмы всех пар кратчайших путей из урока про алгоритм Флойда — Уоршелла: там тоже заполнялась двумерная таблица, где каждая ячейка вычислялась из соседних уже посчитанных ячеек, и ответ на подзадачу для более длинных префиксов строился из ответов для более коротких.

Алгоритм

Рекуррентная формула редакционного расстояния. Пусть $dp[i][j]$ — минимальное число операций, превращающих первые $i$ символов строки $s_1$ в первые $j$ символов строки $s_2$. Тогда:

$$dp[i][j] = \begin{cases} dp[i-1][j-1], & \text{если } s_1[i] = s_2[j] \text{ (символы совпадают, замена не нужна)} \\ 1 + \min\big(dp[i-1][j-1],\ dp[i-1][j],\ dp[i][j-1]\big), & \text{иначе (замена, удаление, вставка)} \end{cases}$$

Базовые случаи: $dp[0][j] = j$ (превратить пустую строку в строку длины $j$ можно только $j$ вставками) и $dp[i][0] = i$ (превратить строку длины $i$ в пустую можно только $i$ удалениями). Три слагаемых внутри минимума соответствуют трём разрешённым операциям: $dp[i-1][j-1]+1$ — замена последнего символа $s_1$ на последний символ $s_2$; $dp[i-1][j]+1$ — удаление последнего символа $s_1$; $dp[i][j-1]+1$ — вставка в $s_1$ символа, совпадающего с последним символом $s_2$.

def levenshtein(s1, s2):
    n, m = len(s1), len(s2)
    dp = [[0] * (m + 1) for _ in range(n + 1)]

    for i in range(n + 1):
        dp[i][0] = i
    for j in range(m + 1):
        dp[0][j] = j

    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if s1[i - 1] == s2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]
            else:
                dp[i][j] = 1 + min(
                    dp[i - 1][j - 1],  # замена
                    dp[i - 1][j],      # удаление
                    dp[i][j - 1],      # вставка
                )

    return dp[n][m]

Именно эта задача, точнее её родственный вариант — алгоритм Нидлмана — Вунша с настраиваемыми весами операций, — используется в биоинформатике для выравнивания последовательностей ДНК и белков, а сам редакционное расстояние в чистом виде — стандартный инструмент NLP: проверка орфографии предлагает исправления, ближайшие по расстоянию Левенштейна к введённому слову; поисковые системы и системы автодополнения используют его для нечёткого сопоставления запроса с известными терминами; системы OCR (распознавание текста по изображению) оценивают качество распознавания через расстояние Левенштейна между распознанным и эталонным текстом.

Разбор примеров

Пример 1 (малый, полная трассировка). Расстояние между «кот» и «кит».

"" к и т
"" 0 1 2 3
к 1 0 1 2
о 2 1 1 2
т 3 2 2 1

Символы «к» и «т» совпадают в обеих строках на своих позициях, а «о» и «и» — нет. Диагональ $dp[1][1]=0$ (оба символа «к» совпали, замена не нужна). Ячейка $dp[2][2]$: символы «о» и «и» не совпадают, минимум из $dp[1][1]+1=1$ (замена), $dp[1][2]+1=2$ (удаление), $dp[2][1]+1=2$ (вставка) — берём 1. Финальная ячейка $dp[3][3]$: символы «т» и «т» совпадают, значит $dp[3][3]=dp[2][2]=1$. Итог: расстояние 1 — единственная замена «о» на «и».

Пример 2 (средний, полная трассировка). Расстояние между «весна» (5 символов) и «весы» (4 символа).

"" в е с ы
"" 0 1 2 3 4
в 1 0 1 2 3
е 2 1 0 1 2
с 3 2 1 0 1
н 4 3 2 1 1
а 5 4 3 2 2

Первые три символа обеих строк совпадают буква в букву («в», «е», «с»), поэтому вся диагональ до $dp[3][3]=0$ заполняется без штрафов. Дальше строки расходятся: у «весна» остаются «н», «а», у «весы» — только «ы». Ячейка $dp[4][3]$ («н» против «с», уже пройденного): $\min(dp[3][2]+1=2,\ dp[3][3]+1=1,\ dp[4][2]+1=3)=1$ — минимум даёт удаление. Ячейка $dp[4][4]$ («н» против «ы»): символы не совпадают, минимум из $dp[3][3]+1=1$ (замена), $dp[3][4]+1=2$ (удаление), $dp[4][3]+1=2$ (вставка) — берём 1. Ячейка $dp[5][4]$ («а» против «ы»): не совпадают, минимум из $dp[4][3]+1=2$, $dp[4][4]+1=2$, $dp[5][3]+1=3$ — берём 2. Итог: $dp[5][4]=\mathbf{2}$ — расстояние между «весна» и «весы» равно 2.

Пример 3 (восстановление последовательности операций). Используя таблицу из примера 2, восстановить конкретные операции редактирования, превращающие «весна» в «весы», обратным проходом от $dp[5][4]$ до $dp[0][0]$.

Стартуем в $dp[5][4]=2$. Символы на этой позиции — $s_1[5]=$«а», $s_2[4]=$«ы», они не совпадают. Проверяем диагональ: $dp[4][3]+1 = 1+1 = 2$ — совпадает с текущим значением, значит последняя операция — замена «а» на «ы». Переходим по диагонали к $dp[4][3]=1$. Символы здесь — $s_1[4]=$«н», $s_2[3]=$«с» — не совпадают. Проверяем варианты: диагональ $dp[3][2]+1=1+1=2 \ne 1$ (не подходит), «удаление» $dp[3][3]+1=0+1=1$ — совпадает с текущим значением! Значит эта операция — удаление символа «н» (шаг «вверх» по таблице, к $dp[3][3]$, без продвижения по второй строке). Переходим к $dp[3][3]=0$. Здесь $s_1[3]=$«с», $s_2[3]=$«с» совпадают — символы просто сохраняются без операции, переходим по диагонали к $dp[2][2]=0$. Далее $s_1[2]=$«е», $s_2[2]=$«е» — снова совпадение, к $dp[1][1]=0$. Наконец $s_1[1]=$«в», $s_2[1]=$«в» — совпадение, переходим к $dp[0][0]=0$, где обе строки исчерпаны, — обратный проход завершён.

Собирая операции в прямом порядке (от начала строки к концу): сохранить «в», сохранить «е», сохранить «с», удалить «н», заменить «а» на «ы». Применяя их к «весна»: в-е-с-(удаляем н)-(а→ы) даёт «в-е-с-ы» = «весы» — ровно целевая строка, и потрачено ровно 2 операции, как и предсказывала таблица.

Почему это важно

Способность не просто посчитать число операций, а восстановить сам список операций — это именно то, что превращает редакционное расстояние из абстрактной метрики в практический инструмент: спелл-чекер не просто сообщает «это слово странное», а показывает, какую букву заменить; система выравнивания геномных последовательностей в биоинформатике выдаёт не число несовпадений, а конкретную карту вставок, делеций и замен вдоль двух цепочек ДНК, по которой биологи делают выводы об эволюционном родстве. И, как ты увидишь в разделе про связь с остальным курсом, эта же самая идея — таблица, заполняемая по рекуррентной формуле, плюс восстановление решения обратным проходом — лежит в основе алгоритма Витерби, только там роль двух строк играют последовательность наблюдений и последовательность скрытых состояний.

Практика: 30 заданий

Базовые задания (1–10)

Задание 1: Сколько вызовов сделает наивная рекурсия для вычисления fib(7) без кэша, если число вызовов вычисляется по формуле $\text{calls}(n) = 2F(n+1) - 1$?

Задание 2: Написать мемоизированную версию функции Фибоначчи на Python с помощью functools.lru_cache.

Задание 3: Заполнить таблицу табуляции для чисел Фибоначчи от fib(0) до fib(8).

Задание 4: Обладает ли сортировка слиянием (merge sort) перекрывающимися подзадачами? Обосновать, почему для неё не нужна мемоизация.

Задание 5: Найти минимальное число монет для суммы 6, если доступны номиналы {1, 3, 4}, заполнив таблицу $dp[0..6]$.

Задание 6: Сколькими способами можно подняться по лестнице из 5 ступенек, если за один шаг можно подниматься на 1 или 2 ступеньки?

Задание 7: Два предмета: вес/ценность $(2,3)$ и $(3,4)$, вместимость рюкзака 4. Заполнить таблицу и найти максимальную ценность.

Задание 8: Найти редакционное расстояние Левенштейна между «да» и «нет».

Задание 9: Своими словами сформулировать два условия, при которых применимо динамическое программирование.

Задание 10: Почему fib(40) в наивной рекурсии выполняется заметно дольше секунды, а с табуляцией — мгновенно?

Средние задания (11–20)

Задание 11: Восстановить порядок заполнения кэша при вычислении fib(6) через мемоизацию (перечислить, в каком порядке появляются записи cache[k]).

Задание 12: Какова временная и пространственная сложность мемоизированного вычисления fib(n), учитывая и кэш, и стек рекурсивных вызовов?

Задание 13: Найти длину наибольшей общей подпоследовательности (LCS) строк «АБВГ» и «АВГД».

Задание 14: Найти минимальное число монет для суммы 11 номиналами {1, 2, 5}.

Задание 15: Сколько существует путей из левого верхнего в правый нижний угол сетки $3\times3$, если двигаться можно только вправо и вниз?

Задание 16: Четыре предмета: вес/ценность $(1,1)$, $(3,4)$, $(4,5)$, $(5,7)$, вместимость рюкзака 7. Найти максимальную ценность.

Задание 17: Объяснить своими словами разницу между мемоизацией и табуляцией и указать по одному практическому преимуществу каждой.

Задание 18: Найти редакционное расстояние Левенштейна между «стол» и «стул».

Задание 19: Объяснить приём сжатия таблицы 0/1 рюкзака с $O(nW)$ памяти до $O(W)$: почему при использовании одномерного массива капасити нужно перебирать в обратном порядке.

Задание 20: Почему для задачи с очень большим, но редко полностью заполняемым пространством состояний (например, рекурсия с отсечениями по дополнительным ограничениям) обычно предпочтительнее мемоизация, а не полная табуляция?

Продвинутые задания (21–30)

Задание 21: Кратко описать формальный вывод рекуррентной формулы редакционного расстояния — почему в случае несовпадающих символов рассматриваются ровно три варианта операций.

Задание 22: Реализовать полное решение 0/1 рюкзака с восстановлением списка выбранных предметов.

Задание 23: Реализовать вычисление редакционного расстояния с восстановлением конкретной последовательности операций (замена/удаление/вставка/совпадение).

Задание 24: Сколькими способами можно набрать сумму 5 монетами номиналов {1, 2, 5}, если важен только набор монет, а не порядок (число комбинаций, а не минимальное число монет)?

Задание 25: Найти длину наибольшей возрастающей подпоследовательности (LIS) массива [3, 1, 4, 1, 5, 9, 2, 6].

Задание 26: Даны три матрицы с размерностями $10\times20$, $20\times30$, $30\times40$. Сравнить число скалярных умножений для двух вариантов расстановки скобок: $(A_1 A_2) A_3$ и $A_1 (A_2 A_3)$.

Задание 27: Воспроизвести рассуждение, почему жадный алгоритм по убыванию удельной ценности $\text{val}/\text{wt}$ даёт неоптимальный результат на предметах $(10,60)$, $(20,100)$, $(30,120)$ при вместимости 50.

Задание 28: Используя таблицу LCS для «АБВГ» и «АВГД» из задания 13, восстановить саму подпоследовательность (а не только её длину) обратным проходом.

Задание 29: Какова временная и пространственная сложность табличного решения задачи о рюкзаке 0/1 с $n$ предметами и вместимостью $W$? Как её понимать при очень большом $W$?

Задание 30: Объяснить, в чём заключается аналогия между рекуррентной формулой динамического программирования и уравнением Беллмана из обучения с подкреплением.

Частые ошибки

Применять ДП к задаче без оптимальной подструктуры. Если оптимальное решение всей задачи не собирается из оптимальных решений подзадач (как в примере с самым длинным простым путём), никакая рекуррентная формула не даст верного ответа — локально оптимальные кусочки могут противоречить глобальному ограничению.

Добавлять кэш к рекурсии, где подзадачи не перекрываются. В таком случае мемоизация не ускоряет программу, а лишь тратит память и время на хэширование аргументов — это симптом того, что задача на самом деле решается обычным «разделяй и властвуй» без ДП.

Путать 0/1 рюкзак с непрерывным (дробным) рюкзаком и применять к первому жадный алгоритм по удельной ценности. Как показано в разборе, жадный выбор даёт заведомо неоптимальный результат именно из-за запрета дробить предметы.

Ошибки на единицу в границах таблицы — особенно в задаче о рюкзаке и редакционном расстоянии, где строка и столбец с индексом 0 соответствуют «нет предметов» или «пустая строка», а не первому реальному предмету или символу. Несогласованность между индексом массива предметов (с нуля) и индексом строки таблицы (с единицы для «первый предмет учтён») — источник систематических ошибок в реализации.

Забывать базовые случаи при мемоизации: если функция не проверяет базовый случай раньше обращения к кэшу или не сохраняет посчитанное значение перед возвратом, кэш просто не работает, а рекурсия остаётся такой же экспоненциальной, как и без него.

Считать только оптимальное значение и забывать, что почти всегда нужно ещё и само решение. Числовой ответ «максимальная ценность — 220» редко бывает конечной целью — как правило, нужен список предметов или последовательность операций, а значит, при проектировании решения сразу стоит подумать, как будет устроен обратный проход или таблица предков.

Переполнение стека рекурсии при мемоизации на больших входах. Для задач с $n$ порядка десятков и сотен тысяч рекурсивная мемоизация в языках с ограниченной глубиной стека (включая Python со стандартным лимитом рекурсии) может упасть с ошибкой там, где итеративная табуляция отработает без проблем.

Главное запомнить

  • Динамическое программирование применимо только при одновременном выполнении двух условий: оптимальной подструктуры и перекрывающихся подзадач; без любого из них нужен другой инструмент.

  • Оптимальная подструктура означает, что оптимальное решение задачи строится из оптимальных решений подзадач; проверяется соответствием между суб-решением, использованным в оптимуме, и отдельно посчитанным оптимумом для той же подзадачи.

  • Перекрывающиеся подзадачи означают, что наивный перебор многократно решает одни и те же меньшие подзадачи — именно это оправдывает затраты на кэш или таблицу.

  • Мемоизация — рекурсия «сверху вниз» с кэшем готовых ответов; вычисляет только реально посещённые состояния.

  • Табуляция — итеративное заполнение таблицы «снизу вверх», от базовых случаев к целевому состоянию; не использует рекурсию и легко поддаётся оптимизации по памяти.

  • Задача о рюкзаке 0/1 — классический пример ДП с двумерным состоянием «номер предмета × остаток вместимости»; жадные алгоритмы для неё в общем случае неоптимальны.

  • Редакционное расстояние Левенштейна вычисляется той же схемой, что и алгоритм Флойда — Уоршелла: заполнение двумерной таблицы по рекуррентной формуле с опорой на уже посчитанные соседние ячейки.

  • Восстановление самого решения (а не только оптимального значения) выполняется обратным проходом по уже заполненной таблице — от финальной ячейки к начальной, сравнивая соседние значения.

  • Табличные решения ДП часто называют псевдополиномиальными: их сложность зависит от числового значения параметра (например, вместимости рюкзака), а не только от длины входа, и это ограничивает применимость при очень больших числовых параметрах.

  • Термин «динамическое программирование» и уравнение Беллмана пришли из теории оптимального управления полутора десятилетиями раньше, чем сложилась современная информатика, и напрямую связаны с уравнением Беллмана в обучении с подкреплением.

Связь с темами курса

Самая прямая связь этого урока с прикладным машинным обучением — алгоритм Витерби, классический пример динамического программирования на графе состояний скрытой марковской модели (HMM). В скрытой марковской модели есть последовательность скрытых состояний (например, фонемы или части речи) и последовательность наблюдений (звуковые кадры или слова), связанные вероятностями переходов между состояниями и вероятностями появления наблюдений в каждом состоянии. Задача — найти наиболее вероятную последовательность скрытых состояний, объясняющую данную последовательность наблюдений. Наивный перебор всех возможных последовательностей состояний длиной $T$ при $N$ возможных состояниях на шаге даёт $N^T$ вариантов — экспоненциальный взрыв, совершенно неприменимый на практике.

Алгоритм Витерби решает эту задачу ровно теми же двумя приёмами, что ты разобрал в этом уроке. Вводится величина $\delta_t(j)$ — вероятность наиболее вероятной последовательности состояний длиной $t$, заканчивающейся в состоянии $j$. Рекуррентная формула $\delta_t(j) = \max_i \big[\delta_{t-1}(i) \cdot P(i{\to}j)\big] \cdot P(\text{наблюдение}_t \mid j)$ — это оптимальная подструктура: лучший путь, заканчивающийся в состоянии $j$ на шаге $t$, строится из лучшего пути, заканчивающегося в каком-то состоянии $i$ на предыдущем шаге. А перекрывающиеся подзадачи здесь — то, что значение $\delta_{t-1}(i)$ для одного и того же состояния $i$ используется при вычислении $\delta_t(j)$ сразу для нескольких разных $j$, поэтому его выгодно посчитать один раз и переиспользовать, вместо того чтобы каждый раз восстанавливать заново. И, как и в задаче о рюкзаке или редакционном расстоянии, одного числа — вероятности наилучшего пути — обычно недостаточно: вместе с $\delta_t(j)$ хранится указатель на то состояние $i$, из которого пришёл максимум, — тот же самый приём восстановления решения обратным проходом, который ты применял для реконструкции набора предметов в рюкзаке и последовательности операций редактирования. Именно алгоритм Витерби лежит в основе классических систем распознавания речи (декодирование фонемной последовательности по акустическому сигналу), разметки частей речи в обработке естественного языка (наиболее вероятная последовательность грамматических тегов для предложения) и поиска генов в биоинформатике — то есть ровно тех задач NLP и обработки последовательностей, к которым ты будешь возвращаться в курсе снова и снова.

Вторая связь — с уроком про алгоритм Флойда — Уоршелла: там ты уже заполнял двумерную таблицу, где каждая ячейка вычислялась через рекуррентную формулу из соседних, ранее заполненных ячеек, а сама задача (кратчайшие пути между всеми парами вершин) обладала теми же двумя свойствами — оптимальной подструктурой и перекрывающимися подзадачами. Редакционное расстояние Левенштейна из этого урока построено по абсолютно той же схеме, только смысл ячеек другой — не расстояние между вершинами графа, а минимальное число операций между префиксами строк.

Третья связь — с областью обучения с подкреплением, где ты позже встретишь уравнение Беллмана в его прямом виде: $V(s) = \max_a \big[R(s,a) + \gamma \sum_{s'} P(s'|s,a) V(s')\big]$. Методы вроде итерации по ценности (value iteration) и итерации по стратегии (policy iteration) — это буквально табуляция, применённая к этому уравнению: таблица ценностей состояний заполняется итеративно, пока не сойдётся, ровно так же, как таблица чисел Фибоначчи заполнялась в этом уроке от меньших индексов к большим.

Интересные факты

Название «динамическое программирование» появилось не из соображений точности термина, а из желания Ричарда Беллмана защитить свою работу от бюрократической критики: слово «динамическое» было выбрано в том числе потому, что его, по признанию самого автора, «почти невозможно было использовать в уничижительном смысле».

Шахматные эндшпильные базы данных (endgame tablebases) — это, по сути, гигантские таблицы динамического программирования: для позиций с малым числом фигур на доске (обычно семь или меньше) заранее вычислен и сохранён точный результат — выигрыш, проигрыш или ничья — для абсолютно каждой такой позиции, а сама таблица заполнялась «от простого к сложному», то есть классической табуляцией снизу вверх, начиная с позиций, где мат уже стоит на доске.

Динамическое программирование лежит в основе того, как сервисы вроде Google Maps учитывают кратчайшие расстояния при построении маршрутов: алгоритмы поиска пути в дорожных графах используют ту же рекуррентную идею «кратчайший путь до перекрёстка строится из кратчайших путей до соседних перекрёстков», что ты уже видел в примере 2 первого раздела этого урока и в прошлых уроках про Дейкстру и Флойда — Уоршелла.

В биоинформатике вариант редакционного расстояния с настраиваемыми весами операций — алгоритм Нидлмана — Вунша (для глобального выравнивания) и алгоритм Смита — Уотермана (для локального выравнивания) — используются буквально миллионы раз в день по всему миру для сравнения последовательностей ДНК, РНК и белков; оба алгоритма представляют собой прямую модификацию таблицы, которую ты заполнял в разделе про Левенштейна.

Лайфхаки

Сначала всегда пиши наивное рекурсивное решение «в лоб», без всякого кэша, и только убедившись, что оно корректно (совпадает с ответом на маленьких, проверяемых вручную примерах), добавляй мемоизацию или переписывай в табуляцию — отлаживать рекуррентную формулу отдельно от оптимизации производительности значительно проще.

Для небольшого $n$ нарисуй дерево рекурсии от руки (или распечатай вызовы) и визуально проверь, повторяются ли в нём одинаковые вызовы, — это быстрее и надёжнее, чем пытаться доказать наличие перекрывающихся подзадач абстрактно.

Перед тем как писать код, явно сформулируй состояние подзадачи словами: «что именно однозначно определяет эту подзадачу?» — если формулировка получается расплывчатой или требует больше параметров, чем ты ожидал, скорее всего рекуррентная формула тоже будет неверной или неполной.

Планируй размерность и объём таблицы заранее, до написания кода: для задач вроде рюкзака с большой вместимостью $O(nW)$ памяти может оказаться неприемлемым — тогда стоит сразу проектировать решение со сжатием до одной строки $O(W)$ или переходить к мемоизации с ограниченным реально достижимым набором состояний.

Если для решения нужен не только оптимум, но и само решение (набор предметов, последовательность операций, путь в графе), с самого начала храни рядом с основной таблицей значений вторую таблицу «откуда пришёл оптимум» (индекс предыдущего состояния или направление перехода) — реконструировать её постфактум по одной таблице значений сложнее и менее надёжно, чем вести её параллельно с заполнением.

Проверяй решение на вырожденных входах отдельно: пустая строка для редакционного расстояния, нулевая вместимость или пустой список предметов для рюкзака, n=0 или n=1 для Фибоначчи — именно на границах чаще всего прячутся ошибки на единицу в индексах таблицы.

Динамическое программирование — это, пожалуй, тот редкий раздел алгоритмики, где интуиция строится не сразу: пока не разберёшь руками десяток задач с таблицами и стрелочками восстановления пути, формула кажется произвольной магией. Но стоит один раз честно провести полную трассировку — построчно, ячейка за ячейкой, как в примерах этого урока, — и способность видеть перекрывающиеся подзадачи и оптимальную подструктуру в новой задаче становится почти рефлекторной. А дальше эта же самая интуиция откроет тебе дорогу и к алгоритму Витерби в распознавании речи и NLP, и к уравнению Беллмана в обучении с подкреплением, и к десяткам других задач, где на первый взгляд экспоненциальный перебор на самом деле прячет за собой аккуратную, полиномиальную по времени таблицу.

Понял тему? Закрепи в боте! 🚀

Попрактикуйся на задачах и получи персональные рекомендации от AI

💪 Начать тренировку
💬 Есть вопрос? Спроси бота!