Двумерный DP: рюкзак, LCS, редактор

Перед началом: базовый DP и Кадане (модуль 16), бинарный поиск (модуль 10 — понадобится для LIS за O(n log n)). Инструменты: Go 1.27, slices. Трудоёмкость: ~6 ч (теория 2.5 ч · практика 3.5 ч).

🔥 Инцидент: «Дифф редактора считался двадцать секунд»

Внутренний редактор показывал различия двух версий документа. Реализация была прямой как палка: перебрать все способы преобразовать строку A в строку B и вернуть самый короткий. На тексте в 100 символов — мгновенно; на реальном файле в 100 килобайт — двадцать секунд и десятки гигабайт виртуальной памяти: экспоненциальный перебор, где каждая позиция разветвляет ещё два варианта.

Классическое «расстояние редактирования» решается таблицей (n+1)×(m+1) за O(n·m): каждая клетка — ответ для пары префиксов, и клетка выражается через трёх соседей. В модуле — двумерный DP во всех прикладных формах: рюкзак, LCS, редактор и LIS, плюс приёмы, без которых таблица либо не влезает в память, либо теряет возможность восстановить ответ.

📖 Теория

17.1 Сетка состояний dp[i][j]

Двумерный DP появляется, когда в состоянии две сущности: предметы и вместимость; префикс A и префикс B; i-я строка и j-й столбец. Ячейка dp[i][j] — ответ для первых i и первых j элементов.

Всегда отвечаем на три вопроса: что в ячейке, через что выражается, в каком порядке заполнять. Порядок почти всегда — строка за строкой слева направо, потому что зависимости смотрят вверх и влево; если зависимость смотрит и «вперёд», порядок придётся менять.

17.2 Рюкзак: предметы и вместимость

0/1-рюкзак: даны предметы с весом w и ценностью v, вместимость W, каждый предмет берём не более раза. Состояние — (предмет, вместимость):

go
// dp[i][c] — лучшая ценность из первых i предметов при вместимости c.
for i := 1; i <= n; i++ {
	w, v := items[i-1].w, items[i-1].v
	for c := 0; c <= W; c++ {
		dp[i][c] = dp[i-1][c] // предмет не берём
		if w <= c && dp[i-1][c-w]+v > dp[i][c] {
			dp[i][c] = dp[i-1][c-w] + v // берём: остаток вместимости
		}
	}
}

1D-сжатие с обратным обходом — классическая ловушка собеседований. Строку можно хранить одной: dp[c], но обход вместимости обязан идти от W вниз. При прямом обходе dp[c-w] уже относится к текущему предмету — это unbounded-рюкзак (предмет можно брать много раз), а не 0/1:

go
for i := 1; i <= n; i++ {
	w, v := items[i-1].w, items[i-1].v
	for c := W; c >= w; c-- { // обратный обход: dp[c-w] ещё из i-1
		if dp[c-w]+v > dp[c] {
			dp[c] = dp[c-w] + v
		}
	}
}

Subset sum — рюкзак без ценностей: dp[s] = true, если суммой предметов набирается s. Задача «есть ли подмножество с суммой S» — тот же переход, только булев.

17.3 LCS и edit distance: диагональ, верх, лево

Две строки — сетка (n+1)×(m+1). Для cat → cut таблица целиком:

Ответ — правая нижняя клетка: одна замена a → u.

Показать кодКопировать код

Формула edit distance: при совпадении символов ячейка берёт диагональ (замена не нужна), иначе — 1 + min(диагональ, верх, лево), где верх — удаление, лево — вставка, диагональ — замена. LCS — родственная сетка: совпали суммы — диагональ +1, иначе максимум из верха и лева.

go
for i := 1; i <= n; i++ {
	for j := 1; j <= m; j++ {
		if a[i-1] == b[j-1] {
			dist[i][j] = dist[i-1][j-1] // символы совпали
		} else {
			dist[i][j] = 1 + min3(dist[i-1][j-1], dist[i-1][j], dist[i][j-1])
		}
	}
}

Восстановление ответа — обратный проход от правой нижней клетки: идём по таблице, повторяя выборы, и собираем операции (или LCS-строку) в обратном порядке. Это вторая причина хранить полную таблицу, а не одну строку.

17.4 LIS: от O(n²) к O(n log n)

Самая длинная возрастающая подпоследовательность — пример того, как DP улучшается вместе с другими инструментами курса.

go
// O(n²): dp[i] — длина LIS, заканчивающейся в a[i].
for i := range a {
	dp[i] = 1
	for j := 0; j < i; j++ {
		if a[j] < a[i] && dp[j]+1 > dp[i] {
			dp[i] = dp[j] + 1
		}
	}
	best = max(best, dp[i])
}

За O(n log n) — через вспомогательный массив tails, где tails[k] — минимально возможный последний элемент возрастающей подпоследовательности длины k+1. Он всегда строго возрастает, а значит, обновляется бинарным поиском (sort.SearchInts, модуль 10):

go
tails := []int{}
for _, v := range a {
	i := sort.SearchInts(tails, v) // первый >= v
	if i == len(tails) {
		tails = append(tails, v) // удлиняем подпоследовательность
	} else {
		tails[i] = v // улучшаем хвост: меньше — лучше для будущего
	}
}
// len(tails) — длина LIS.

Внимание: tails — не сама подпоследовательность, а «хвосты». Для восстановления LIS нужны дополнительные индексы-родители.

17.5 Строковые и интервальные DP

• Палиндромные подстроки и подпоследовательности — сетка по подстрокам s[i..j]; состояние «i..j палиндром?» заполняется от коротких интервалов к длинным.
• Wildcard matching (? и *) — та же сетка, но переходы зависят от шаблона: * умеет «съесть» и пусто, и очередной символ.
• Интервальный DP — состояние «интервал [i, j]», переход — разрез интервала в точке k. Так решаются «ломание строки», «баллон с шариками», «минимальный разрез палиндрома». Порядок заполнения — по длине интервала, а не по строке.

Общее правило: заметив, что состоянием становится пара индексов, вы почти всегда в мире интервального DP с порядком «от коротких интервалов к длинным».

17.6 Компромиссы

💻 Практика

1. Рюкзак в двух видах. Реализуйте 0/1-рюкзак таблицей (n+1)×(W+1) и сжатием до одного среза с обратным обходом. Тест: на 20 фиксированных наборах оба ответа совпадают. Затем сломайте сжатие прямым обходом и покажите на одном наборе, что получается unbounded-рюкзак.
2. Subset sum. Есть ли подмножество с суммой S? Решите булевым DP, затем сожмите до битовой маски uint64 (64 суммы на слово) для S < 64 — во сколько раз меньше памяти.
3. LCS с восстановлением. Реализуйте таблицу и обратный проход, возвращающий саму подпоследовательность (не только длину). Тесты: общая вставка, отсутствие общих символов, полное совпадение.
4. Редактор с операциями. Edit distance, возвращающий и число, и последовательность операций (вставка, удаление, замена) в прямом порядке. Проверьте на cat → cut (одна замена) и kitten → sitting (три операции).
5. LIS двумя способами. O(n²) и O(n log n) на одном массиве; сравните число операций (счётчиком) и убедитесь в одинаковом ответе. Отдельно: массив из 10 000 элементов — O(n²) ещё терпим, O(n log n) мгновенен.

🧩 Quiz

✅ Итоги модуля

• Двумерный DP — сетка состояний по двум сущностям; три вопроса (что в ячейке, через что выражается, в каком порядке заполнять) решают, как её строить.
• 0/1-рюкзак сжимается до O(W) только с обратным обходом; прямой обход превращает его в unbounded.
• LCS и edit distance — переходы по диагонали, верху и лево; восстановление ответа — обратный проход по полной таблице.
• LIS улучшается с O(n²) до O(n log n) массивом tails плюс бинарный поиск — прямая перекличка с модулем 10.
• Интервальный DP и строковые задачи — тот же двумерный каркас с порядком по длине интервала.

🔗 Мостик к Модулю 18

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