Экономия памяти

Время динамики — произведение числа состояний на стоимость перехода, и уменьшить его обычно нельзя, не поменяв алгоритм. А вот память уменьшается почти всегда, и делается это механически.

Считать заранее полезно: таблица $10^4 \times 10^4$ из int — это 400 МБ, то есть отказ по памяти при типичном лимите 256 МБ. Таблица $10^3 \times 10^5$ из long long — 764 МБ.

Две строки

Если переход смотрит только на предыдущую строку, вся таблица не нужна.

vector<int> prev(m + 1, 0), cur(m + 1, 0);
for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++)
        cur[j] = (a[i - 1] == b[j - 1]) ? prev[j - 1] + 1
                                        : max(prev[j], cur[j - 1]);
    swap(prev, cur);
}
// ответ лежит в prev — после последнего swap

Проверено: на 20 000 досках до $8 \times 8$ результат совпадает с полной таблицей.

Замер на НОП двух строк по 5000 символов: полная таблица int — 95 МБ, две строки — 0,04 МБ, время 45 мс.

Две ловушки. Первая: swap векторов в C++ меняет местами внутренние указатели и стоит $O(1)$ — копирования нет. Писать prev = cur вместо этого можно, но это лишнее копирование на каждой строке.

Вторая: после цикла ответ лежит в prev, а не в cur — последний swap уже произошёл. Ошибка тихая: программа выводит значение предпоследней строки.

Одна строка

Иногда хватает и одного массива — если аккуратно выбрать направление обхода. Классика — рюкзак:

for (int i = 0; i < n; i++)
    for (int j = W; j >= w[i]; j--)
        d[j] = max(d[j], d[j - w[i]] + c[i]);

Идея та же, что с двумя строками, только «предыдущая строка» — это те ячейки, до которых обход ещё не добрался. Обходя веса по убыванию, мы читаем слева ячейки старого слоя; обходя по возрастанию — уже обновлённые.

Поэтому свёртка в один массив возможна не всегда, а только когда переход смотрит строго в одну сторону по второму индексу. Если он смотрит и влево, и вправо — нужны две строки.

Проверьте себя вопросом: «какое значение я читаю — до обновления или после?» Если ответ «до» и это правильно — обход выбран верно.

Хранить только по модулю

Когда переход смотрит на $k$ строк назад, держат $k + 1$ строку и обращаются по циклическому индексу.

vector<vector<long long>> d(3, vector<long long>(m + 1, 0));
for (int i = 0; i <= n; i++) {
    // d[i % 3] считается через d[(i - 1) % 3] и d[(i - 2) % 3]
}

Приём выручает в задачах вида «нельзя ставить одинаковое ближе чем через $k$». Единственное, о чём надо помнить: перед вычислением новой строки её надо очистить — там лежат данные с шага $i - k - 1$, и они не нули.

Пропущенная очистка — одна из самых неприятных ошибок в динамике: ответ получается почти правильным, потому что мусор влияет не на все состояния.

Чем платят

Восстановлением ответа. По двум строкам не проследить путь. Если условие просит сам ответ, а не его величину, есть три выхода:

• держать таблицу целиком, если она влезает;
• хранить не значения, а только направления переходов — обычно это два бита на состояние, в восемь раз меньше int;
• делить пополам по Хиршбергу: посчитать половину таблицы слева, половину справа, найти точку стыка, рекурсивно разобрать обе половины. Памяти $O(\min(n, m))$, времени вдвое больше.

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

Когда экономить не надо

Если таблица помещается — не сворачивайте. Свёртка стоит времени на написание, ломает восстановление ответа и вносит ошибки, которые ищутся дольше, чем экономится памяти.

Считайте до, а не после: перемножьте размеры, умножьте на размер типа, сравните с лимитом. Восемь мегабайт таблицы — это норма, сто — повод свернуть.

И держите в голове разницу между int и long long: она вдвое, и иногда именно она решает. Если ответ заведомо мал, а промежуточные значения — нет, полезно посмотреть, где на самом деле нужен большой тип.