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

Рекурсия с мемоизацией: как это работает?

Сначала напишите обычную рекурсию. Добейтесь правильности до попыток ускорить.

Посмотрите, что на самом деле является аргументами. Если два вызова их делят, ответ у них общий.

Добавьте кеш с ключом по этим аргументам. Подойдёт и словарь, и обычный массив.

В начале функции возвращайте сохранённый ответ, если он есть. Дальше ничего не выполняется.

Перед возвратом сохраните ответ под его ключом. Следующий вызов прочитает его вместо пересчёта.

Теперь каждый различный аргумент считается один раз. Дерево вызовов схлопывается в граф.

1. fib(5) требует fib(4) и fib(3)Наивная версия расходится на два вызова.
2. fib(4) требует fib(3) и fib(2)Теперь fib(3) нужен уже дважды.
3. кеш = {2: 1, 3: 2}Первый fib(3) посчитан и сохранён.
4. fib(3) это чтение из кешаВторой fib(3) читает кеш. Всё его поддерево пропущено.
5. 15 вызовов стали 9Без кеша fib(50) занял бы миллиарды вызовов.

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;
}

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

Наименьшее число монет на сумму

Даны номиналы монет и сумма. Верните наименьшее число монет, дающее эту сумму.

Если набрать сумму нельзя, верните минус один.

Задайте тот же вопрос про меньшую сумму. Каждая монета даёт одну ветку.

Подзадачу определяет только остаток суммы. Значит по нему и делается ключ кеша.

function coinChange(coins, amount) {
    const cache = new Map();

    function best(left) {
        if (left === 0) return 0;
        if (left < 0) return Infinity;
        if (cache.has(left)) return cache.get(left); // computed before

        let answer = Infinity;
        for (const coin of coins) {
            answer = Math.min(answer, best(left - coin) + 1);
        }

        cache.set(left, answer); // store the failure too
        return answer;
    }

    const result = best(amount);
    return result === Infinity ? -1 : result;
}

Рекурсия с мемоизацией: когда применять?

Эти формулировки в условии ведут сюда:

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

Рекурсия с мемоизацией: с чем путают?

• Рекурсия (Recursion): Обычная рекурсия каждый раз пересчитывает повторный аргумент. Кеш это вся разница.
• Динамическое программирование (1-D) (Dynamic programming (1-D)): Динамика снизу заполняет таблицу в заданном порядке. Здесь она заполняется по требованию, сверху.
• Хеш-множество / словарь (Hash set / map): Кешем обычно служит словарь. Эта страница про то, когда его вообще заводить.
• Бэктрекинг (Backtracking): Бэктрекинг обходит пути, которые все разные, поэтому ничего не повторяется. Кеш там хранит ключи, которых больше не спросят.

Рекурсия с мемоизацией: частые ошибки

• В ключ не попал один из аргументов

  В ключ входит всё, от чего зависит ответ. Неполный ключ вернёт ответ другого вызова.

• Кешируют изменяемый объект

  Сохранённую ссылку может испортить более поздний вызов. Храните копию или простое значение.

• Не кешируют неудачу

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

• Кешируют там, где ничего не повторяется

  Если все аргументы разные, кеш только тратит память. Сначала проверьте пересечение подзадач.

Рекурсия с мемоизацией: задачи с собеседований

• Числа Фибоначчи: Кратчайший пример пересекающихся подзадач.
• Подъём по лестнице: Та же форма с другим базовым случаем.
• Размен монет: Ключ это оставшаяся сумма.
• Ограбление домов: Ключ это индекс, на котором вы стоите.
• Разбиение строки на слова: Ключ это позиция начала в строке.
• Число путей в сетке: Ключ это пара координат.
• Самый длинный возрастающий путь в матрице: Ключ это клетка, и множество посещённых не нужно.

Рекурсия с мемоизацией: сложность по времени и памяти

O(states)

Стоимость это число различных аргументов на работу одного вызова. Кеш в 1e6 ключей нормален.