Мемоизация и ленивая динамика

Наивная рекурсия для чисел Фибоначчи работает за экспоненту:

long long fib(int n) {
    if (n <= 2) return 1;
    return fib(n - 1) + fib(n - 2);
}

Причина не в рекурсии как таковой, а в повторах: fib(3) при вычислении fib(5) считается дважды, fib(2) — трижды. Дерево вызовов растёт как $\varphi^n$.

Лечится одной строкой.

Приём

Заведём массив ответов, заполненный «не посчитано», и будем возвращать готовое значение, если оно уже есть.

vector<long long> memo(MAX_N + 1, -1);

long long fib(int n) {
    if (n <= 2) return 1;
    if (memo[n] != -1) return memo[n];
    return memo[n] = fib(n - 1) + fib(n - 2);
}

Теперь в глубину функция проваливается для каждого $n$ ровно один раз, и всё решение стоит $O(n)$. Проверено: fib(50) считается мгновенно и равно $12\,586\,269\,025$.

Приём называется мемоизацией — от «memory», а не от «меморизация». Буквы «р» в слове нет.

Строка return memo[n] = ... делает две вещи сразу: присваивает и возвращает. Так короче и, что важнее, невозможно забыть про присваивание.

Выбор маркера «не посчитано»

$-1$ работает, только если ответ не может быть отрицательным. Если может — берите значение, которое ответом быть не способно, или заводите отдельный массив флагов bool computed.

Второй вариант надёжнее и стоит один байт на состояние. Не экономьте на нём, если хоть немного сомневаетесь: ошибка «маркер совпал с настоящим ответом» проявляется на редких тестах и ищется тяжело.

Зачем это на самом деле

Для Фибоначчи мемоизация — избыточность, цикл проще. Настоящая её ценность в другом: не нужно знать порядок обсчёта.

Классический пример — задача о ходах коня. Конь ходит из левого верхнего угла в правый нижний, разрешены четыре хода, каждый — вправо-вниз в широком смысле. Сколько путей?

Пересчитывать динамику по строкам нельзя: клетке нужны значения, которых в предыдущей строке ещё нет. По столбцам — тоже. Правильный порядок существует (по диагоналям), но до него надо додуматься, а потом ещё аккуратно написать.

С мемоизацией порядок не нужен вовсе:

long long paths(int i, int j) {
    if (i == 0 && j == 0) return 1;
    if (min(i, j) < 0 || max(i, j) >= n) return 0;
    if (memo[i][j] != -1) return memo[i][j];
    return memo[i][j] = paths(i - 2, j + 1) + paths(i - 2, j - 1)
                      + paths(i - 1, j - 2) + paths(i + 1, j - 2);
}

Запускаем от правого нижнего угла, и рекурсия сама выясняет, что от чего зависит.

Проверено: для досок от $1 \times 1$ до $8 \times 8$ этот код даёт ровно то же, что обсчёт по диагоналям.

Такая запись динамики называется ленивой: значения считаются по требованию, а не заранее.

Обязательное условие

Ленивая динамика работает тогда и только тогда, когда правильный порядок обсчёта существует — то есть в зависимостях нет циклов.

Знать этот порядок не нужно, но существовать он обязан. Если состояние прямо или косвенно зависит от самого себя, рекурсия уйдёт в бесконечность и упрётся в переполнение стека.

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

Когда не надо

Освоив ленивую динамику, хочется писать так всё. Не стоит.

Она медленнее. Вызов функции дороже итерации цикла, а обращения к памяти идут вразнобой — кэш работает плохо. Разница доходит до нескольких раз.

Она тратит стек. Глубина рекурсии равна длине цепочки зависимостей. Для динамики по массиву из $10^6$ элементов это переполнение.

Она отучает думать. Порядок обсчёта — часто и есть содержательная часть решения; поняв его, вы обычно видите и способ сэкономить память.

Разумное правило: порядок очевиден — пишите цикл, порядок неочевиден — пишите лениво. Если состояние двумерное и переходы идут «вперёд» по обеим координатам, порядок очевиден. Если переходы идут в разные стороны, как у коня, — ленивая динамика проще и надёжнее.

Мемоизация по словарю

Когда состояний много, но достижимо из них мало, массив не завести. Тогда берут словарь:

map<pair<long long, int>, long long> memo;

long long solve(long long value, int step) {
    auto key = make_pair(value, step);
    auto found = memo.find(key);
    if (found != memo.end()) return found->second;
    // ...
    return memo[key] = result;
}

Это дороже массива на логарифм и на большую константу, зато позволяет состояния вида «остаток от деления», «маска», «пара больших чисел» — там, где массив занял бы терабайты. Типичный пример — динамика по цифрам числа до $10^{18}$.