Алгоритмы с нуля
Dynamic programming: чтение кода
Суть Читаем реальные DP-сниппеты: найдите баг кэша, неверный state, небезопасную оптимизацию памяти и настоящую сложность — диагноз, который senior ставит до доверия любой DP.
Высота — путь к senior
НольJuniorMiddleSenior
Ты на middle-высоте — в небеБаги в DP молчаливы — они возвращают уверенно неверное число, а не падение. Прочитайте каждый сниппет, предскажите, что он на самом деле считает, и выберите исправление, которое senior сделает первым.
Цель
Отработайте цикл, который вы запускаете на каждой DP: проверить, что ключ кэша совпадает с полным state, что transition покрывает каждый выбор, что оптимизация памяти не разрушает ещё нужное значение, и считать настоящую сложность по циклам.
Сниппет 1 — memo, который не попадает
def lcs(a, b):
memo = {}
def go(i, j):
if i == len(a) or j == len(b):
return 0
if a in memo: # баг: ключ не тот
return memo[a]
if a[i] == b[j]:
res = 1 + go(i + 1, j + 1)
else:
res = max(go(i + 1, j), go(i, j + 1))
memo[a] = res
return res
return go(0, 0) Викторина
Completed
Эта memoization LCS одновременно неверна и медленна. В чём дефект и как исправить?
Heads-up Пустая subsequence имеет длину 0; возврат 1 завысил бы счёт. Базовый случай верен — дефект в ключе кэша.
Heads-up LCS берёт лучший из двух вариантов пропуска, так что max верен. Сумма задвоила бы пересекающиеся subsequence. Баг — в ключе кэша.
Heads-up Глубина тут не больше len(a)+len(b), что нормально для обычных входов. Настоящий баг — ключевание кэша по a вместо (i, j).
Сниппет 2 — state в coin-change
def min_coins(coins, amount):
# одна монета на номинал, без повторов
dp = [0] + [float('inf')] * amount
for c in coins:
for x in range(amount, c - 1, -1): # ёмкость вниз
dp[x] = min(dp[x], dp[x - c] + 1)
return dp[amount] if dp[amount] != float('inf') else -1 Викторина
Completed
Автор хочет НЕОГРАНИЧЕННОЕ использование каждой монеты (классический coin change). Делает ли это 1D-код, и что задаёт направление обхода?
Heads-up Направление именно и разделяет два варианта. Вниз (0/1) запрещает повтор монеты в одном проходе; вверх (unbounded) разрешает. Здесь обход вниз даёт неверный ответ «не более раза».
Heads-up dp[0]=0 верно: нулём монет набирают сумму 0. Дефект — обход вниз, который тихо ограничивает каждую монету одним использованием.
Heads-up Порядок монет не влияет на корректность этой DP. Дефект — направление цикла, выбирающее семантику 0/1 вместо unbounded.
Сниппет 3 — оптимизация скользящей строки
def edit_distance(a, b):
n, m = len(a), len(b)
prev = list(range(m + 1)) # строка для i = 0
for i in range(1, n + 1):
cur = [i] + [0] * m # cur[0] = i
for j in range(1, m + 1):
if a[i - 1] == b[j - 1]:
cur[j] = prev[j - 1]
else:
cur[j] = 1 + min(prev[j], cur[j - 1], prev[j - 1])
prev = cur
return prev[m] Викторина
Completed
Этот код edit distance сворачивает 2D-таблицу до двух строк. Корректна ли оптимизация памяти и какая зависимость делает её безопасной?
Heads-up Каждая ячейка читает лишь предыдущую строку и левого соседа текущей, так что двух строк хватает. Полная таблица нужна, только если надо восстановить сам сценарий правок.
Heads-up cur и prev — отдельные массивы, запись cur[j-1] не трогает prev[j-1]. Диагональ prev[j-1] цела для следующего столбца. Оптимизация безопасна.
Heads-up Ничего не приближается; три чтения (prev[j], cur[j-1], prev[j-1]) — это ровно те же значения, что в полной таблице. Тот же ответ, меньше памяти.
Сниппет 4 — циклы interval DP
def interval_cost(n, weight):
dp = [[0] * n for _ in range(n)]
for length in range(2, n + 1): # длина интервала
for i in range(0, n - length + 1): # левый конец
j = i + length - 1 # правый конец
best = float('inf')
for k in range(i, j): # точка разбиения
best = min(best, dp[i][k] + dp[k + 1][j] + weight(i, k, j))
dp[i][j] = best
return dp[0][n - 1] Викторина
Completed
Какова временная и пространственная сложность этой interval DP и откуда берётся доминирующая стоимость?
Heads-up Вложенных циклов три: длина, левый конец и точка разбиения k. Внутренний перебор разбиений и поднимает до O(n^3), а не O(n^2).
Heads-up Время O(n^3), но память — лишь таблица dp размером n на n, то есть O(n^2). Третьего измерения не хранится.
Heads-up Разбиения пробуются, но каждый (i, j) считается один раз и кэшируется в dp, так что это полином. Экспонента — это наивная рекурсия без таблицы.
Итог
Четыре проверки ловят большинство дефектов DP: ключ кэша должен равняться полному state подзадачи (Сниппет 1 ключевал по неверной переменной); transition и направление цикла должны совпадать с задуманной семантикой (Сниппет 2 — вниз это 0/1, вверх это unbounded); сжатие до скользящей строки безопасно, лишь когда ячейка читает только предыдущую строку и соседей текущей (Сниппет 3); а настоящая сложность — произведение границ циклов: O(n^2) state на O(n) работы на state даёт O(n^3) (Сниппет 4). Читайте циклы, а не комментарий.