Динамическое программирование: базовый уровень

Перед началом: рекурсия и перебор с возвратом (модуль 7), скользящее окно и префиксные суммы (модуль 3). Инструменты: Go 1.27, срезы, map. Трудоёмкость: ~5 ч (теория 2 ч · практика 3 ч).

🔥 Инцидент: «Пятнадцать строк рекурсии положили сервис»

В биллинге появилась функция «число способов собрать сумму купонами» — пятнадцать строк, прямой рекурсивный перебор: на каждом шаге пробуем каждый купон. На тестах с суммами до 40 всё было мгновенно. Первый же клиент с суммой 300 превратил запрос в 20-секундный CPU-шторм: рекурсия заново пересчитывала одни и те же подсуммы, число вызовов росло экспоненциально — 2ⁿ путей по почти одинаковым ветвям.

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

📖 Теория

16.1 Когда задача пахнет DP

DP применим, когда выполняются два условия:

• перекрывающиеся подзадачи — одна и та же подзадача всплывает в разных ветвях (в инциденте: сумма 137 встречается в десятках путей);
• оптимальная подструктура — ответ собирается из ответов на меньшие подзадачи (минимум монет для 137 — это 1 + минимум для 136).

Границы с соседними техниками:

Определяющий вопрос: влияет ли выбор сейчас на будущее? Если да — состояние DP. Если нет — вероятно, хватит жадного.

16.2 Мемоизация: рекурсия плюс кэш

Мемоизация сохраняет рекурсию как есть и добавляет память результатов. Изменения минимальны: проверить кэш в начале, положить в него перед возвратом.

go
var calls int // счётчик вызовов — цена без кэша видна на числах

func fibMemo(n int, memo []int) int {
	calls++
	if n <= 1 {
		return n
	}
	if memo[n] != -1 {
		return memo[n] // подзадача уже решена
	}
	memo[n] = fibMemo(n-1, memo) + fibMemo(n-2, memo)
	return memo[n]
}

Кэш по состоянию: если состояние — одно число, подойдёт срез []int (O(1) доступ, ноль хеширования); если состояние составное (индекс и лимит, две строки) — map[[2]int]int или таблица по обоим измерениям.

16.3 Табуляция: порядок важнее рекурсии

Табуляция идёт снизу вверх: сначала база, дальше состояния в порядке, при котором все зависимости уже посчитаны. Рекурсия и стек исчезают, зато нужно самому выстроить порядок.

go
// climbStairs: число способов подняться на n ступеней шагами 1 и 2.
func climbStairs(n int) int {
	if n <= 2 {
		return n
	}
	dp := make([]int, n+1)
	dp[1], dp[2] = 1, 2
	for i := 3; i <= n; i++ {
		dp[i] = dp[i-1] + dp[i-2] // база → переход → порядок
	}
	return dp[n]
}

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

16.4 Одномерный набор: где DP встречается каждый день

Четыре задачи, которые покрывают большинство 1D-случаев:

go
// 1. Минимальная стоимость подъёма: шагаем с cost[i] дальше на 1–2.
//    dp[i] = cost[i] + min(dp[i-1], dp[i-2])

// 2. Дома с сигнализацией (house robber): нельзя брать две подряд.
//    dp[i] = max(dp[i-1], dp[i-2] + a[i])

// 3. Минимум монет до суммы s (coin change):
//    dp[s] = 1 + min(dp[s-coin]) по всем монетам <= s

// 4. Максимальная сумма подотрезка (Кадане):
//    cur = max(a[i], cur + a[i]) — dp[i] «максимум, заканчивающийся в i»

Кадане стоит поставить рядом с модулем 3: там мы говорили, что при отрицательных числах окно не работает. Вот инструмент, который его заменяет: cur = max(a[i], cur+a[i]) — это DP-состояние «лучший подотрезок, заканчивающийся ровно здесь».

coin change в двух вариантах — важное различие:

• минимум монет — «оптимизация», классический DP;
• число способов — «подсчёт комбинаций», тот же dp, но сумма по вариантам выбора, и порядок перебора монет влияет на то, считаем ли мы комбинации или перестановки.

16.5 Память: от таблицы к двум переменным

Если dp[i] зависит только от dp[i-1] и dp[i-2], вся таблица не нужна: две переменные дают ту же асимптотику по времени и O(1) по памяти.

go
// Кадане без таблицы: O(1) памяти.
func maxSubarray(a []int) int {
	best, cur := a[0], a[0]
	for _, v := range a[1:] {
		if cur += v; cur < v {
			cur = v // «начинаем заново» — состояние dp[i] = v
		}
		if cur > best {
			best = cur
		}
	}
	return best
}

Правило: оптимизацию памяти делают в конце, когда решение проверено на таблице. Сначала таблица — чтобы видеть переходы; потом сжатие — и снова прогнать тесты.

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

💻 Практика

1. Фибonacci с измеримой ценой. Напишите три версии: чистая рекурсия, мемоизация, табуляция. Счётчик вызовов должен напечатать разницу на n = 30: порядок величин будет нагляднее любых слов.
2. Классический набор. Реализуйте climbStairs (шаги 1–2 и обобщение на произвольный набор шагов), minCostClimbingStairs и houseRobber с тестами на границы: n = 0, n = 1, отрицательные значения.
3. Coin change в двух вариантах. (а) минимум монет; (б) число комбинаций. Проверьте, что для (б) смена порядка циклов «монеты внешним» против «сумма внешним» меняет ответ на перестановки — и объясните почему.
4. Кадане и его окно. Решите max subarray DP-формулой и покажите на примере с отрицательным числом, почему скользящее окно из модуля 3 здесь не работает (монотонности нет), а dp-состояние — работает.
5. Сжатие памяти. Возьмите решение задачи 2 с таблицей и сожмите до O(1). Убедитесь, что тесты проходят на тех же данных; замерьте аллокации до и после (или посчитайте обращения к срезу).

🧩 Quiz

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

• DP — про перекрывающиеся подзадачи и оптимальную подструктуру; вопрос «влияет ли выбор на будущее» отделяет DP от жадного и от перебора.
• Мемоизация = рекурсия + кэш; табуляция = база, переход, порядок; обе дают одну асимптотику с разными разменами (стек против явной таблицы).
• 1D-набор (лестница, дома, монеты, Кадане) покрывает большинство прикладных случаев; Кадане закрывает дыру окна на отрицательных числах.
• Таблицу сжимают до O(1) только после того, как решение проверено в полном виде.

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

Одномерных состояний не хватает, как только в задаче появляются две сущности: предметы и вместимость, две строки, текст и шаблон. В модуле 17 — «Двумерный DP: рюкзак, LCS, редактор»: таблица dp[i][j], переход через диагональ, верх и лево, восстановление ответа обратным проходом и 1D-сжатие с обратным обходом, которое застаёт врасплох почти каждого.