Алгоритмы с нуля
Двумерная ДП: пути в сетке, LCS, расстояние редактирования
Одномерные ДП что ты видел до сих пор имели одну подвижную часть: состояние было одним числом, как dp[i], и ты заполнял одну строку значений. Но огромное семейство задач нуждается в двух индексах сразу. Сколько есть способов пройти из левого верхнего угла сетки в правый нижний? Насколько похожи две строки? Как малым числом правок превратить kitten в sitting? У каждой из них есть подзадача описанная двумя позициями — строкой и столбцом, или индексом в каждую строку. Состояние становится dp[i][j], а кэш становится двумерной таблицей. Механизм идентичен одномерной ДП — определи состояние, напиши рекуррентность, зафиксируй базовые случаи, заполни в порядке, прочитай ответ — только по сетке, а не по линии.
После этого урока ты можешь распознать когда задаче нужно двумерное состояние dp[i][j] и выстроить соответствующую двумерную таблицу. Ты можешь точно определить состояние (что значит dp[i][j]), написать рекуррентность из соседей клетки, зафиксировать базовую строку и базовый столбец, выбрать порядок заполнения так чтобы зависимости каждой клетки были уже вычислены, и прочитать ответ в правом нижнем углу. Ты можешь проработать три классики по памяти: число уникальных путей в сетке (dp[i][j] = dp[i-1][j] + dp[i][j-1]), наибольшую общую подпоследовательность (dp[i-1][j-1]+1 при совпадении, иначе max(dp[i-1][j], dp[i][j-1])), и расстояние редактирования (вставка, удаление или замена). Ты знаешь что сложность это O(m·n) по времени и O(m·n) по памяти, и ты можешь ужать память до O(min(m,n)) скользящим массивом, потому что каждая строка зависит только от строки выше. Следующий блок выходит за пределы сеток к более общим формам ДП.
Когда состоянию нужны два индекса
В двумерной ДП подзадачу нельзя описать одним числом — ей нужны два. Состояние это dp[i][j], где i и j это две независимые позиции: строка и столбец в сетке, или индекс в каждую из двух строк. Поскольку состояние это пара, кэш это двумерная таблица (массив массивов), и ты заполняешь её в двух вложенных циклах вместо одного.
Всё остальное это тот же пятишаговый рецепт что и одномерная ДП:
- Определи состояние. Скажи одним предложением что значит
dp[i][j]. Это самый трудный и самый важный шаг — сделай его правильно и рекуррентность выпадет сама. - Напиши рекуррентность. Вырази
dp[i][j]через клетки которые ты уже заполнил (обычноdp[i-1][j],dp[i][j-1],dp[i-1][j-1]). - Установи базовые случаи. Заполни первую строку и первый столбец напрямую — у них нет “предыдущей” клетки на которую опереться.
- Выбери порядок заполнения. Зацикли так чтобы зависимости каждой клетки были вычислены до неё. Сверху вниз, слева направо работает всякий раз когда клетка зависит только от клеток сверху и слева.
- Прочитай ответ. Это почти всегда правая нижняя клетка,
dp[m][n]— состояние для полной задачи.
Классика 1: уникальные пути в сетке
Робот стартует в левом верхнем углу сетки m × n и может двигаться только вправо или вниз. Сколько различных путей достигают правого нижнего угла? Определи dp[i][j] = число путей от старта до клетки (i, j). Чтобы достичь (i, j) твой последний ход пришёл либо сверху (i-1, j), либо слева (i, j-1), так:
dp[i][j] = dp[i-1][j] + dp[i][j-1]База: вся первая строка и первый столбец это 1 (только один прямолинейный способ достичь любую краевую клетку). Ответ это dp[m-1][n-1]. Сетка 3 × 3:
c0 c1 c2
r0 1 1 1
r1 1 2 3
r2 1 3 6 <- 6 paths to bottom-rightКлассика 2: наибольшая общая подпоследовательность (LCS)
Подпоследовательность сохраняет символы в порядке но может пропускать некоторые (без перестановки). LCS находит самую длинную последовательность появляющуюся в обеих строках. Определи dp[i][j] = длина LCS первых i символов A и первых j символов B. Сравни последние символы каждого префикса:
if A[i-1] == B[j-1]: dp[i][j] = dp[i-1][j-1] + 1 // match: extend the diagonal
else: dp[i][j] = max(dp[i-1][j], dp[i][j-1]) // mismatch: drop one charБаза: строка 0 и столбец 0 это все 0 (LCS с пустой строкой пуста). Ответ это dp[m][n]. Заполненная таблица для A = ABCBDAB, B = BDCAB:
'' B D C A B
'' 0 0 0 0 0 0
A 0 0 0 0 1 1
B 0 1 1 1 1 2
C 0 1 1 2 2 2
B 0 1 1 2 2 3
D 0 1 2 2 2 3
A 0 1 2 2 3 3
B 0 1 2 2 3 4 <- LCS length 4 (e.g. "BCAB" or "BDAB")Заметь что +1 читает диагональ dp[i-1][j-1], а max читает клетку сверху и клетку слева. Эти три соседа это сердце каждой строковой ДП.
Классика 3: расстояние редактирования (Левенштейна)
Расстояние редактирования это минимальное число односимвольных операций вставки, удаления или замены чтобы превратить строку A в строку B. Определи dp[i][j] = расстояние редактирования между первыми i символами A и первыми j символами B. Если последние символы совпадают, новая правка не нужна; иначе возьми самую дешёвую из трёх операций и добавь единицу:
if A[i-1] == B[j-1]: dp[i][j] = dp[i-1][j-1]
else: dp[i][j] = 1 + min(
dp[i-1][j], // delete A[i-1]
dp[i][j-1], // insert B[j-1]
dp[i-1][j-1] ) // replace A[i-1] with B[j-1]Базовые случаи несут здесь настоящий смысл: dp[i][0] = i (удали все i символов чтобы достичь пустой строки) и dp[0][j] = j (вставь все j символов из ничего). Ответ это dp[m][n]. kitten → sitting это 3 (замени k→s, замени e→i, вставь g).
Общая форма
Все три определяют dp[i][j], заполняют базовую строку и базовый столбец, потом заполняют внутренность из уже-вычисленных соседей, и читают ответ в правом нижнем углу. Уникальные пути складывают двух соседей; LCS и расстояние редактирования комбинируют диагональ плюс двух ортогональных соседей. Как только ты видишь этот паттерн, большинство задач ДП на сетках и строках выглядят одинаково.
Наибольшая общая подпоследовательность, снизу вверх
Состояние это пара (i, j), так кэш это таблица (m+1) × (n+1). Лишняя строка и столбец держат базовый случай пустого префикса (все нули), вот почему индексы в строки это A[i-1] и B[j-1].
1
function lcs(a, b) {
2
const m = a.length, n = b.length;
3
// (m+1) x (n+1) table; row 0 and col 0 are the empty-prefix base (all 0)
4
const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));
5
6
for (let i = 1; i <= m; i++) {
7
for (let j = 1; j <= n; j++) {
8
if (a[i - 1] === b[j - 1]) {
9
dp[i][j] = dp[i - 1][j - 1] + 1; // match: extend the diagonal
10
} else {
11
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]); // mismatch: drop one char
12
}
13
}
14
}
15
return dp[m][n]; // answer is the bottom-right cell
16
}
- L2 m и n это длины двух строк.
- L4 Выдели двумерную таблицу размером (m+1) на (n+1), заполненную нулями.
- L6 Внешний цикл проходит строки i = 1..m; строка 0 остаётся нулевым базовым случаем.
- L7 Внутренний цикл проходит столбцы j = 1..n; столбец 0 остаётся нулевым базовым случаем.
- L8 Сравни последние символы двух префиксов: A[i-1] и B[j-1].
- L9 Совпадение: LCS растёт на один за диагональной клеткой dp[i-1][j-1].
- L11 Несовпадение: лучшее из отбрасывания последнего символа A (сверху) или последнего символа B (слева).
- L15 Состояние полной задачи dp[m][n] это длина LCS.
Ключевой момент: таблица на один размер больше строк
У таблицы m+1 строк и n+1 столбцов, не m и n. Индекс 0 каждой оси это пустой префикс, чья LCS равна 0. Эта лишняя граница и есть то что позволяет рекуррентности читать dp[i-1][j-1] даже когда i или j равно 1 не сваливаясь с таблицы.
Запуск
Расстояние редактирования, та же форма с тремя вариантами
Расстояние редактирования переиспользует ровно ту же структуру таблицы — меняются только рекуррентность и базовая строка/столбец. Здесь базовые случаи ненулевые: превращение префикса длины i в пустую строку стоит i удалений, так dp[i][0] = i, и симметрично dp[0][j] = j.
Давай заполним таблицу LCS для короткой пары A = "AB", B = "AC". Таблица 3 × 3 (одна лишняя строка и столбец для пустого префикса). Строка 0 и столбец 0 начинаются с 0. Мы заполняем строка за строкой, слева направо, наблюдая как каждая внутренняя клетка читает трёх своих соседей (сверху, слева, по диагонали).
1
for i in 1..m:
2
for j in 1..n:
3
if A[i-1] == B[j-1]:
4
dp[i][j] = dp[i-1][j-1] + 1
5
else:
6
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
Время: O(m·n)
В таблице (m+1) × (n+1) клеток, что это O(m·n). Каждая клетка делает O(1) работы: сравнение и max или min по фиксированному числу соседей. Так общее время это
total time = (number of states) x (work per state) = O(m*n) x O(1) = O(m*n)Для двух строк длины 1000 это около миллиона вычислений клеток — быстро. Это то же правило сложности что и одномерная ДП (различные состояния умножить на работу на состояние); единственное изменение это что число состояний теперь произведение двух размерностей, а не одной.
Память: O(m·n), ужимаемая до O(min(m, n))
Полная таблица хранит каждую клетку, так прямолинейная версия использует O(m·n) памяти. Но посмотри на рекуррентности: dp[i][j] читает только из строки i и строки i-1. Она никогда не касается строки i-2 или раньше. Так тебе нужно держать только две строки за раз — текущую и предыдущую — и перезаписывать по ходу. Это приём скользящего массива:
full table: O(m*n) space (keep every row)
two rows: O(n) space (keep current + previous row)
one row: O(n) space (overwrite carefully, saving the diagonal in a temp)Чтобы сделать хранимую строку меньшей размерностью, зацикли с более короткой строкой по столбцам; тогда память это O(min(m, n)). Загвоздка: скользящие строки дают тебе только финальное число. Если тебе также нужно восстановить саму подпоследовательность или сценарий правок, ты должен держать полную таблицу O(m·n) чтобы пройтись по ней назад.
time space gives the path back?
full 2D table O(m*n) O(m*n) yes
rolling rows O(m*n) O(min(m,n)) no (number only)Скачок от 1D к 2D
Ментальная модель не меняется от 1D: посчитай различные состояния, умножь на работу на состояние. У одномерной ДП по n было n состояний и O(n) время. У двумерной ДП по сетке m × n есть m·n состояний и O(m·n) время. Если будущей задаче понадобились бы три индекса, таблица была бы трёхмерной а время O(m·n·p) — то же правило, больше размерностей.
В подсчёте уникальных путей в сетке, какая рекуррентность для dp[i][j] (пути до клетки (i,j)), если ходы могут быть только вправо или вниз?
Для наибольшей общей подпоследовательности, чему равно dp[i][j] когда последние символы совпадают, то есть A[i-1] == B[j-1]?
В расстоянии редактирования, почему базовые случаи dp[i][0] = i и dp[0][j] = j (а не все нули как у LCS)?
После заполнения двумерной таблицы ДП сверху вниз и слева направо, где ты читаешь ответ для полной задачи?
Почему память двумерной ДП часто можно сократить с O(m*n) до O(min(m,n))?
Вычисление расстояния редактирования между двумя строками длины 200 и 300 заполняет таблицу (200+1) x (300+1). Сколько это клеток?
Почему это работает
Зачем лишняя строка и столбец? Таблица это (m+1) × (n+1), не m × n. Строка и столбец с индексом 0 представляют пустой префикс каждой строки. Без них рекуррентность dp[i-1][j-1] сваливалась бы с таблицы всякий раз когда i или j равно 1. Граница кодирует наименьший базовый случай (LCS с пустой = 0; расстояние редактирования с пустой = другая длина) и даёт каждой внутренней клетке валидного соседа для чтения. Вот почему индексы строк появляются как A[i-1] и B[j-1]: строка таблицы i соответствует символу строки i-1.
Частая ошибка
Неправильный порядок заполнения, или чтение неправильного соседа. Двумерная рекуррентность корректна только если зависимости каждой клетки уже заполнены когда ты до неё доходишь. dp[i][j] зависящая от dp[i-1][j], dp[i][j-1] и dp[i-1][j-1] безопасна с циклами сверху вниз, слева направо — но если бы рекуррентность когда-нибудь читала dp[i+1][j] тебе понадобилось бы противоположное направление. Вторая частая оплошность это путаница трёх соседей: случай совпадения читает диагональ dp[i-1][j-1], случай несовпадения читает сверху и слева. Перестановка их молча производит неправильные ответы которые всё равно “выглядят” правдоподобно на малых входах.
Граничные случаи
Пустые строки и идентичные строки. Если любая из строк пуста, ответ немедленен из базовых случаев: LCS это 0, а расстояние редактирования это длина непустой строки. Если строки идентичны, LCS равна их длине а расстояние редактирования равно 0. Эти крайности это ровно то что кодируют базовая строка и столбец, так корректная таблица обрабатывает их без особых случаев. Всегда проверяй свой код на пустом входе и на двух равных входах — они ловят большинство ошибок на единицу и ошибок базового случая.
Ещё практика
Рецепт двумерной ДП. (1) Напиши одно предложение определяющее dp[i][j]. (2) Из этого определения выведи рекуррентность спрашивая “какие выборы ведут в состояние (i,j)?” — обычно клетки сверху, слева и по диагонали. (3) Заполни базовую строку и базовый столбец напрямую из определения. (4) Зацикли сверху вниз, слева направо чтобы зависимости были готовы. (5) Прочитай dp[m][n]. Потом оптимизируй: если тебе нужно только финальное число а не восстановленный путь, сверни к скользящему массиву для O(min(m,n)) памяти. Тренируйся заполняя вручную таблицы уникальных путей и расстояния редактирования для крошечных входов прежде чем доверять коду.
Объясни как работает двумерная ДП: состояние, почему у таблицы лишняя строка и столбец, рекуррентности LCS и расстояния редактирования, где живёт ответ, и сложность по времени и памяти.
Двумерная ДП для задач чьей подзадаче нужны два индекса: состояние это dp[i][j] а кэш это двумерная таблица.
Пятишаговый рецепт (тот же что 1D, по сетке): определи что значит dp[i][j]; напиши рекуррентность из уже-заполненных соседей (сверху dp[i-1][j], слева dp[i][j-1], по диагонали dp[i-1][j-1]); заполни базовую строку и базовый столбец; зацикли сверху вниз, слева направо; прочитай ответ в правом нижнем углу dp[m][n].
Три классики:
- Уникальные пути:
dp[i][j] = dp[i-1][j] + dp[i][j-1], базовая строка и столбец все 1. - LCS:
dp[i-1][j-1]+1при совпадении, иначеmax(dp[i-1][j], dp[i][j-1]), базовая граница все 0. - Расстояние редактирования:
dp[i-1][j-1]при совпадении, иначе1 + min(удаление, вставка, замена), базаdp[i][0]=i,dp[0][j]=j.
Лишняя строка и столбец держат базовый случай пустого префикса чтобы у граничной рекуррентности был валидный сосед; символ строки i сидит в строке таблицы i+1.
Сложность: O(m·n) по времени (состояния умножить на O(1) работы). Память O(m·n), ужимаемая до O(min(m,n)) скользящим массивом потому что каждая клетка зависит только от текущей и предыдущей строки — но держи полную таблицу если тебе нужно восстановить сам путь.
Следующий блок выходит за пределы сеток и строк к более общим формам ДП построенным на той же дисциплине состояние-рекуррентность-база-заполнить-прочитать.