Как ужать память в ДП с двумя слоями (хранить только dp[i] и dp[i-1])?
Заполняю таблицу dp[i][j], и переход зависит только от строки i-1 (например, рюкзак или DP на сетке). При больших n ловлю MLE на двумерном массиве. Как корректно свести к двум одномерным слоям или даже к одному, не сломав логику?
2 ответа
Если dp[i][*] зависит только от dp[i-1][*], храним два слоя prev и cur и свопаем их. Память падает с $O(n\cdot m)$ до $O(m)$.
vector<long long> prev_(m + 1), cur(m + 1);
// инициализация prev_ как dp[0][*]
for (int i = 1; i <= n; ++i) {
for (int j = 0; j <= m; ++j)
cur[j] = /* функция от prev_[...] и cur[...] */;
swap(prev_, cur); // O(1) — меняем указатели векторов
}
// ответ в prev_ после последней итерации
Часто можно ужать и до одного массива, если порядок обновления j исключает использование уже перезаписанных значений текущего слоя. Классика — 0/1 рюкзак в 1D, где цикл по вместимости идёт по убыванию, чтобы каждый предмет учёлся один раз:
vector<long long> dp(W + 1, 0);
for (int i = 0; i < n; ++i)
for (int w = W; w >= wt[i]; --w) // строго по убыванию!
dp[w] = max(dp[w], dp[w - wt[i]] + cost[i]);
Память $O(W)$, время не меняется $O(nW)$.
Два правила, которые экономят от багов:
- Направление цикла решает всё. В 0/1 рюкзаке 1D — по убыванию
w(иначе предмет «размножится» — это уже неограниченный рюкзак). В неограниченном рюкзаке, наоборот, по возрастаниюw— и это фича, а не баг. swapслоёв — O(1) дляstd::vector(меняет внутренние указатели), не копирование. Не пишиprev_ = cur;в цикле — это $O(m)$ копирование на каждой итерации, лишний множитель.
И помни: ужатие до 2/1 слоёв убивает возможность простого восстановления ответа (нужны все слои). Если ответ восстанавливать обязательно — либо храни доп. массив выборов, либо применяй D&C-восстановление (Хиршберг).