Как перевести рекурсию с мемоизацией в итеративное ДП и не потерять корректность порядка?
У меня есть рабочее решение через рекурсию + unordered_map/массив memo, но оно ловит TLE (накладные на рекурсию/хеш) или Stack Overflow на больших данных. Хочу переписать в итеративную табуляцию. Как механически определить правильный порядок заполнения и где обычно ошибаются?
2 ответа
Алгоритм перевода почти механический:
- Состояние → измерения массива. Аргументы рекурсии становятся индексами таблицы
dp[...]. - База рекурсии → инициализация соответствующих ячеек.
- Порядок заполнения = обратный топологический порядок зависимостей. Если
f(x)вызываетf(x-1), заполняй по возрастаниюx. В interval DPf(i,j)зовёт более короткие отрезки → внешний цикл по длине. Правило: к моменту вычисленияdp[s]всеdp, от которых оно зависит, уже посчитаны.
Пример — обычная одномерная рекуррента (число способов забраться по лестнице):
// рекурсия: f(i) = f(i-1) + f(i-2), f(0)=f(1)=1
vector<long long> dp(n + 1);
dp[0] = 1; dp[1] = 1;
for (int i = 2; i <= n; ++i)
dp[i] = dp[i - 1] + dp[i - 2]; // зависимости уже готовы
Итеративный вариант убирает накладные рекурсии, хеш-таблицы и риск переполнения стека. Сложность по времени та же, что у мемоизации (число состояний × стоимость перехода), но константа меньше и память предсказуема (обычный массив вместо unordered_map).
Где спотыкаются:
- Неверный порядок вложенных циклов. Особенно в interval DP и ДП на подмасках. В bitmask DP, где
dp[mask]зависит от подмасок, маски надо идти по возрастанию (подмаска < маски как число при добавлении бита) — проверяй, что переход всегда «вперёд». - Забыли инициализировать недостижимые состояния «нейтральным» значением (0 для счёта, $\pm\infty$ для min/max). Иначе мусор протечёт в ответ.
- Память. Иногда мемоизация спасала на разреженных состояниях (
map), а плотная таблица не влезает. Тогда либо оставляй мемоизацию, но итеративную (через явный стек), либо сжимай измерения.
Компромисс: если состояний мало, но они разрежены — мемоизация с map может быть лучше плотной таблицы. Табуляция выигрывает, когда пространство состояний плотно заполняется.