Рекурсия с мемоизацией

O(states)

Рекурсивная функция кеширует результат по своим аргументам, так что повторяющаяся подзадача считается один раз, а не экспоненциальное число раз.

Сигналы

рекурсивные вызовы повторяют одни и те же аргументы (пересекающиеся подзадачи)обычная рекурсия работает верно, но слишком медленно / экспоненциальный взрывмало различных состояний, хотя дерево рекурсии огромноезакешировать результат (i, ...) перед возвратомформулировка вроде Фибоначчи / подъём по лестнице / путь по сетке с намёком на кеш

Шаблон

function fib(n, memo = new Map()) {
    if (n <= 1) return n;
    if (memo.has(n)) return memo.get(n);
    const result = fib(n - 1, memo) + fib(n - 2, memo);
    memo.set(n, result);
    return result;
}

Похоже, но не то

Обычная рекурсия: Обычная рекурсия пересчитывает одно и то же состояние заново каждый раз, и это нормально, если состояния не повторяются. За мемоизацию берутся, только когда замечают, что одни и те же аргументы встречаются в дереве вызовов не один раз.
Динамическое программирование (таблица): Мемоизация это то же самое рекуррентное соотношение, решённое сверху вниз с кешем. На таблицу снизу вверх переходят, когда хотят избежать глубины рекурсии или заполнить таблицу в фиксированном порядке.

n/состояний до примерно 1e4-1e5, и наивная рекурсия много раз заходит в одно и то же (i, j) -> кешируем каждое состояние один раз: O(состояний) по времени и памяти вместо экспоненты.

Изучить этот паттерн