Память: одна строка вместо таблицы и чем за это платишь

Если ты знаешь, когда таблица сворачивается до строки, что при этом теряется и что такое приём Хиршберга, листай до «Теперь сам».

Как думаешь, сколько строк таблицы нужно одновременно

Посмотри на переход рюкзака: dp[i][c] зависит от dp[i−1][c] и dp[i−1][c − вес]. Обе ссылки - в предыдущую строку. На строку i−2 не ссылается никто.

Прежде чем читать дальше: если строки 0...i−2 больше никому не нужны, зачем они лежат в памяти? И что именно мы потеряем, если их не хранить?

На что это похоже

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

Механизм: когда сворачивается и что теряется

ПРИЗНАК: на какие строки ссылается переход

dp[i] = f(dp[i−1])                 → хватит ДВУХ переменных
dp[i] = f(dp[i−1], dp[i−2])        → хватит ДВУХ значений (Фибоначчи: a и b,
                                     плюс временная c для обмена)
dp[i][c] = f(dp[i−1][...])         → хватит ОДНОЙ строки (обход назад)
                                     или двух (если порядок внутри строки важен)
dp[i][j] = f(dp[i−1][...], dp[i][j−1]) → двух строк (LCS)
dp нужен весь для восстановления   → не свернуть, или приём Хиршберга

ЗАМЕР - сколько клеток нужно
рюкзак, n = 40, C = 120:        4961  →  121     в 41 раз меньше
LCS, строки 200 и 300:        60 501  →  602     в 100 раз меньше
Фибоначчи, n = 10⁶:            10⁶    →  2       константа

ЧТО ТЕРЯЕТСЯ
восстановление ответа. Обратный проход требует СРАВНЕНИЯ клеток разных
строк (dp[i][c] против dp[i−1][c]) - а предыдущих строк больше нет.
Остаётся только число

Правило

Таблица сворачивается тогда, когда переход ссылается на ограниченное число предыдущих строк: достаточно хранить ровно их. Рюкзак - одна строка с обходом вместимости назад, LCS - две строки, Фибоначчи - две переменные. Экономия линейна по числу выброшенных строк: у рюкзака на 40 предметах память падает в 41 раз, у LCS на строках 200 и 300 - в сто. Плата одна: по свёрнутым ЗНАЧЕНИЯМ восстановить сам ответ нельзя, остаётся только число - обойти это можно таблицей РЕШЕНИЙ (стрелки) или Хиршбергом. Если нужны и ответ, и память, берут приём Хиршберга - делить задачу пополам по одной из строк: Θ(n·m) времени и Θ(n+m) памяти при вдвое большей константе. И общее правило: сворачивать стоит последним шагом, когда правильность уже проверена на полной таблице.

Разбор: LCS в двух строках

Переход LCS ссылается на dp[i−1][j−1], dp[i−1][j] и dp[i][j−1] - то есть на предыдущую строку и на текущую слева. Значит нужны ровно две строки:

prev = [0] * (m + 1)
i = 1
while i <= n:
    cur = [0] * (m + 1)
    j = 1
    while j <= m:
        if a[i - 1] == b[j - 1]:
            cur[j] = prev[j - 1] + 1
        else:
            if prev[j] > cur[j - 1]:
                cur[j] = prev[j]
            else:
                cur[j] = cur[j - 1]
        j = j + 1
    prev = cur
    i = i + 1
# ответ в prev[m]

ЗАМЕР: строки по 200 и 300 символов
полная таблица    60 501 клетка
две строки           602 клетки      в 100 раз меньше, ответ тот же

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

А теперь то, чего сделать нельзя: восстановить саму подпоследовательность. Обратный проход сравнивает dp[i−1][j] с dp[i][j−1], то есть читает клетки по всей таблице, а у нас остались две последние строки. Ответ «ЛГРИМ» из прошлой главы получить уже не выйдет - только его длину 5.

Разбор: приём Хиршберга - и ответ, и память

Если ответ нужен, а памяти нет, задачу разрезают пополам. Идея: взять середину первой строки, i = n/2, и найти, на каком месте j вторую строку разрезал бы оптимальный ответ.

ШАГ 1. посчитать LCS префиксов: строки a[1..n/2] со ВСЕМИ префиксами b
       - это одна строка таблицы, Θ(m) памяти

ШАГ 2. посчитать LCS суффиксов: строки a[n/2+1..n] со всеми СУФФИКСАМИ b
       - тоже одна строка

ШАГ 3. точка разреза j - там, где сумма этих двух величин максимальна

ШАГ 4. рекурсивно решить две половины: (a[1..n/2], b[1..j]) и
       (a[n/2+1..n], b[j+1..m]), склеить ответы

ЦЕНА
время: n·m + n·m/2 + n·m/4 + ... = 2·n·m   ⇒  Θ(n·m), константа вдвое больше
память: Θ(n + m) - на каждом уровне рекурсии по две строки,
        плюс стек глубины log n

Вот и ответ на вопрос «можно ли получить и то и другое»: можно, ценой удвоения времени. Именно этот приём стоит в библиотечных реализациях diff для больших файлов - там полная таблица не влезает в память, а ответ нужен обязательно.

практическая развилка
нужно число          → сворачивай, это бесплатно
нужен ответ, памяти хватает → полная таблица, обратный проход
нужен ответ, памяти нет     → Хиршберг (вдвое дольше)

Что ломается без этого

Первое: свернуть таблицу и потом обнаружить, что нужен сам ответ - переписывать придётся всё. Поэтому порядок работы такой: сначала полная таблица, проверка правильности, и только потом сворачивание. Второе: свернуть рюкзак и забыть развернуть обход вместимости - про это весь прошлый урок. Третье: у LCS писать в ту же строку, не сохранив диагональное значение: cur[j−1] уже перезаписан, и переход читает не то. Четвёртое: считать, что экономия памяти ускоряет: число операций то же, но на больших таблицах выигрыш в кеше бывает заметным - это надо мерить, а не предполагать. Пятое: применять Хиршберга к задаче, где переход ссылается не только на соседнюю строку: приём работает, когда таблица «слоистая». Шестое: сворачивать мемоизацию - там память и есть кеш, и выкидывать из него нельзя ничего, пока рекурсия не закончилась.

Зачем это в работе

Свёртка таблицы - самая частая и самая безопасная оптимизация в этой теме: она не меняет ни правильность, ни асимптотику по времени, а памяти экономит в десятки раз. Два практических сюжета. Первый - ограничение памяти: LCS двух файлов по 50 тысяч строк - это 2,5 миллиарда клеток полной таблицы, десятки гигабайт. Свёртка снимает именно ПАМЯТЬ: 2,5 миллиарда операций при этом остаются, и для файлов всё равно берут алгоритм, цена которого зависит от размера различий (прошлая глава). То есть свёртка делает задачу решаемой по памяти, но не делает её быстрой. Второй - встраиваемые системы и горячий код: там часто важнее не время, а объём занятой памяти, и ДП с одной строкой - стандартный приём. Отдельно стоит знать про Хиршберга: когда коллега говорит «diff на больших файлах не влезает в память», правильный ответ - не «увеличим лимит», а «посчитаем по Хиршбергу вдвое дольше и в линейной памяти».

Теперь сам

Переход задачи: dp[i][j] = min(dp[i−1][j], dp[i][j−1], dp[i−1][j−1]) + стоимость(i, j). Сколько строк надо хранить и можно ли восстановить сам путь?

prev - строка i−1
cur  - строка i, заполняется слева направо
    cur[j] = min(prev[j], cur[j−1], prev[j−1]) + cost(i, j)

полная таблица значений     n·m чисел (4-8 байт каждое)
таблица стрелок             n·m пар бит - в 16-32 раза меньше
две строки значений         2·m чисел, но путь не восстановить