Алгоритмы с нуля
Мемоизация: нисходящий DP, кэшируй рекурсию
В прошлом уроке ты видел как наивный Фибоначчи взрывается: fib(30) стоил 2,7 миллиона вызовов потому что одни и те же маленькие подзадачи решались снова и снова. Решение звучит почти слишком просто. Оставь рекурсию ровно как есть. Добавь один блокнот. Перед тем как вычислить fib(n), загляни в блокнот — если ответ уже там записан, просто прочитай его. Иначе вычисли его, запиши и верни. Этот блокнот это кэш, а прикручивание его к рекурсии называется мемоизация. Тот же fib(30) падает с 2,7 миллиона вызовов до 59.
После этого урока ты можешь реализовать динамическое программирование нисходящим способом с мемоизацией: возьми естественную рекурсию и добавь кэш по аргументам подзадачи. Ты можешь назвать три шага внутри мемоизированной функции — сначала проверь кэш, вычисли при промахе, сохрани перед возвратом — и объяснить почему каждый нужен. Ты можешь выбрать структуру кэша: массив когда состояние это маленькие неотрицательные целые числа, Map иначе. Ты понимаешь почему это называется “нисходящим”: ты начинаешь от цели и спускаешься рекурсией к базовым случаям, заполняя кэш на обратном пути вверх. Ты можешь сформулировать правило сложности для любого мемоизированного DP: время равно числу отдельных состояний на работу на состояние, а память включает и кэш, и стек рекурсии. Ты можешь применить мемоизацию ко второму примеру (подъём по лестнице) чтобы увидеть как шаблон обобщается. Следующий урок это табуляция (урок 03): тот же DP вычисленный восходящим способом циклом, без стека рекурсии.
Что это мемоизация?
Мемоизация это нисходящий способ писать динамическое программирование. Ты берёшь естественное рекурсивное решение — то которое ты написал бы в любом случае — и добавляешь кэш который запоминает каждый ответ при первом вычислении. Рекурсия остаётся той же; кэш просто не даёт ей перерешать подзадачи которые она уже решила.
Мемоизированная функция делает ровно три вещи, в таком порядке:
- Проверь кэш. Если ответ для этого входа уже сохранён, верни его немедленно. (Это попадание в кэш которое экономит всю работу.)
- Вычисли при промахе. Если он не сохранён, запусти обычный рекурсивный случай чтобы вычислить его.
- Сохрани, потом верни. Перед возвратом запиши ответ в кэш чтобы следующий вызов с тем же входом попал на шаг 1.
Это весь шаблон. Мемоизация = рекурсия + “проверь кэш, потом сохрани в кэш”.
Ключ кэша это состояние подзадачи
Кэш индексируется теми аргументами которые полностью описывают подзадачу — её состоянием. Для Фибоначчи состояние это просто одно число n, так что fib(7) всегда означает ту же подзадачу и может кэшироваться по ключу 7. Если подзадаче нужны два аргумента (скажем клетка сетки (row, col)), ключом была бы пара. Два вызова с одним состоянием должны вернуть один ответ; именно это делает кэширование корректным.
Почему это “нисходящий”
Мемоизация запускает рекурсию как написано, так что она начинает с верха — цели которую ты действительно хочешь, как fib(30) — и спускается рекурсией вниз к базовым случаям (fib(0), fib(1)). Ответы заполняются на обратном пути вверх: самые глубокие вызовы завершаются первыми, сохраняют свои результаты, и каждый уровень выше читает эти сохранённые результаты вместо их перевычисления. Ты никогда не планируешь порядок; рекурсия сама обнаруживает какие подзадачи ей нужны и решает их по требованию. (Табуляция из урока 03 делает наоборот: она начинает с базовых случаев и строит вверх к цели циклом.)
Выбор структуры кэша
Используй простейшую структуру которую позволяет состояние:
- Массив когда состояние это маленькие неотрицательные целые числа, как
fib(n)дляnот 0 до N. Индексация массива быстра и ключи плотные. Инициализируй записи сигнальным значением (undefined) чтобы ты мог отличить “ещё не вычислено” от настоящего сохранённого значения. - Map (или хеш-таблица) когда состояние это не маленькое целое — отрицательные числа, строки, большие или разреженные ключи, или кортежи превращённые в строковые ключи как
`${row},${col}`. Map обрабатывает любой ключ но стоит немного больше за поиск.
Правило большого пальца: массив если можешь индексировать его напрямую и дёшево; иначе Map.
Почему это сворачивает экспоненту в линию
Существует только n+1 отдельных подзадач Фибоначчи: fib(0) до fib(n). Наивная рекурсия игнорирует это и перестраивает всё дерево, вычисляя каждую подзадачу много раз — экспоненциально. Мемоизация вычисляет каждую отдельную подзадачу ровно раз (первый вызов) и читает её из кэша каждый другой раз (попадание). Так общая реальная работа это одно вычисление на отдельное состояние. n+1 состояний, константная работа каждое, даёт O(n).
Naive recursion: fib(k) recomputed many times -> ~2^n calls
Memoized (top-down): fib(k) computed once, then cached -> ~2n calls, O(n) workМемоизированный Фибоначчи (нисходящий)
Это наивная рекурсия из урока 01 с прикрученным кэшем. Состояние это одно целое n, а n это маленькое неотрицательное целое, так что кэш это массив.
1
function fib(n, memo = []) {
2
// Base cases: fib(0) = 0, fib(1) = 1
3
if (n <= 1) {
4
return n;
5
}
6
// 1. Check the cache: if fib(n) is already known, return it (a hit)
7
if (memo[n] !== undefined) {
8
return memo[n];
9
}
10
// 2. Miss: compute it with the normal recursive case
11
const result = fib(n - 1, memo) + fib(n - 2, memo);
12
// 3. Store before returning, so the next call with this n hits the cache
13
memo[n] = result;
14
return result;
15
}
- L3 Базовые случаи останавливают рекурсию: fib(0)=0 и fib(1)=1. Кэширование им не нужно.
- L7 Шаг 1 — проверь кэш. undefined значит 'ещё не вычислено'; любое другое значение это настоящий сохранённый ответ.
- L8 Попадание в кэш: верни сохранённый ответ немедленно и пропусти всю рекурсивную работу.
- L11 Шаг 2 — промах кэша: запусти естественную рекурсию. Переданный вниз кэш значит что эти вызовы тоже мемоизированы.
- L13 Шаг 3 — сохрани результат по ключу n ПЕРЕД возвратом, так что позже вызовы с тем же n попадают в кэш.
- L14 Верни вычисленный ответ.
Ключевой момент: кэш общий вниз по рекурсии
memo передаётся в каждый рекурсивный вызов, так что все вызовы пишут в и читают из одного кэша. Первый раз когда fib(3) вычислен он сохраняется; каждый поздний запрос на fib(3) — из любой ветки — читает его обратно. Эта общая память это то что убивает повторную работу.
Запуск: смотри как счёт вызовов сворачивается
Тот же fib(30) что в прошлом уроке. Наивная рекурсия взяла 2 692 537 вызовов. Мемоизированная версия вычисляет каждую из 31 отдельной подзадачи раз.
Оба возвращают тот же ответ, 832040. Наивный сделал 2,7 миллиона вызовов; мемоизированный сделал 59. Эти 59 это около 2n − 1 (один вычисляющий вызов плюс один вызов попал-и-вернул на каждое сохранённое значение): экспоненциальное дерево было обрезано до тонкой линии кэшем.
Второй пример: подъём по лестнице
Шаблон обобщается на любую рекурсию с перекрывающимися подзадачами. Подъём по лестнице спрашивает: сколько отдельных способов подняться на n ступеней если ты делаешь 1 или 2 шага за раз? Рекуррента это ways(n) = ways(n-1) + ways(n-2) — та же форма что Фибоначчи — потому что последний ход это либо шаг на 1 (со ступени n−1) либо шаг на 2 (со ступени n−2). Базовые случаи: ways(1) = 1 (одна ступень, один способ), ways(2) = 2 (1+1 или 2). Состояние снова одно целое n, так что кэш снова массив, и применяются те же три шага.
Идентичная механика — проверь, вычисли, сохрани — превращает эту экспоненциальную рекурренту в O(n) тоже. Как только ты можешь распознать состояние и рекурренту, мемоизация механична.
Давай протрассируем начало fib(5) мемоизированного и посмотрим как кэш заполняется на пути вниз, потом производит попадания на обратном пути. Кэш начинается пустым: memo = [].
1
function fib(n, memo = []) {
2
if (n <= 1) return n;
3
if (memo[n] !== undefined) return memo[n];
4
memo[n] = fib(n - 1, memo) + fib(n - 2, memo);
5
return memo[n];
6
}
Время: O(n)
Кэш гарантирует что каждая отдельная подзадача вычисляется только раз. Существует n+1 отдельных состояний (fib(0) до fib(n)), а работа на вычисление каждого — одно сложение двух кэшированных значений — это O(1). Общее правило для любого мемоизированного DP такое:
total time = (number of distinct states) x (work per state)Для Фибоначчи это (n+1) состояний x O(1) работы = O(n). Каждый другой вызов это попадание в кэш, которое тоже O(1) и ничего не перевычисляет. Конкретно, запуск выше сделал 59 вызовов для fib(30): примерно 2n вызовов вместо наивных 2,7 миллиона.
Память: O(n) — кэш плюс стек рекурсии
Мемоизация платит памятью на двух фронтах, и оба важны:
- Кэш держит одну запись на отдельное состояние: O(n) для Фибоначчи.
- Стек рекурсии уходит так глубоко как самая длинная цепь незавершённых вызовов. Первый спуск идёт fib(n) -> fib(n-1) -> … -> fib(0) перед тем как что-либо вернётся, так что стек достигает глубины O(n).
Итого память это O(n). Глубина стека это подвох: для очень больших n глубокая нисходящая рекурсия может переполнить стек вызовов, хотя время линейное. Табуляция из урока 03 убирает рекурсию полностью (простой цикл), так что она держит кэш O(n) но платит никакой стоимости стека — и часто может сжать кэш до O(1).
time cache stack
naive recursion O(2^n) none O(n)
memoization O(n) O(n) O(n) <- this lesson
tabulation O(n) O(n)->O(1) O(1) <- next lessonОбщий рецепт сложности
Для любого DP который ты мемоизируешь, ты не считаешь узлы дерева рекурсии. Ты считаешь отдельные состояния и умножаешь на работу на состояние. Подсчёт путей в сетке над сеткой r x c имеет r·c состояний, O(1) работы каждое, так O(r·c) время и O(r·c) кэш. Найди состояние, сосчитай его, умножь — это весь анализ сложности.
Что мемоизация добавляет к простой рекурсии чтобы сделать её динамическим программированием?
Внутри мемоизированной функции, в каком порядке должны происходить три шага?
Почему мемоизация называется 'нисходящим' подходом?
Когда массив это правильная структура кэша, и когда стоит использовать Map вместо?
Какое общее правило для временной сложности мемоизированного DP?
Помимо кэша, какую другую стоимость памяти несёт нисходящая мемоизация которую табуляция не несёт?
Мемоизированный DP имеет 100 отдельных состояний и делает O(1) работы на состояние. Примерно сколько вычислений состояний он выполняет всего (считая каждое отдельное состояние раз)?
Почему это работает
Почему мемоизация до табуляции? Мемоизация обычно более лёгкая первая версия потому что тебе не надо вычислять правильный порядок заполнения таблицы — рекурсия обнаруживает его за тебя. Ты пишешь естественное рекурсивное решение, добавляешь кэш, и оно просто работает. Табуляция (урок 03) часто быстрее на практике (нет накладных расходов рекурсии, нет стека) и может сжать память, но она заставляет тебя упорядочить подзадачи вручную. Частый рабочий процесс такой: напиши рекурсию, мемоизируй её чтобы получить корректное O(n) решение, потом конвертируй в табуляцию если тебе нужна скорость или меньший стек.
Частая ошибка
Ошибка: сохранение после возврата, или вовсе нет. Если ты вычисляешь ответ и return его не записав сначала в кэш, каждый будущий вызов с теми же аргументами промахивается мимо кэша и перевычисляет всё поддерево — ты получаешь накладные расходы рекурсии без всякой экономии, иногда всё ещё экспоненциально. Всегда сохраняй, потом возвращай. Связанная ловушка это проверка кэша слишком поздно (после рекурсивных вызовов), которая тоже тратит попадание. Проверяй сначала, сохраняй последним.
Граничные случаи
Сигнальное значение для “ещё не вычислено”. С массивом-кэшем отличай “ответ не сохранён” от законно сохранённого ответа 0. if (memo[n] !== undefined) работает потому что пустой слот массива читается как undefined. Но если ты наивно написал бы if (memo[n]), сохранённый fib(0) = 0 выглядел бы ложным и трактовался бы как промах, перевычисляя его навсегда. Выбери сигнальное значение (undefined, null или -1) которое никогда не может быть настоящим ответом, и проверяй против него явно.
Ещё практика
Рецепт для любого мемоизированного DP. (1) Напиши простую рекурсию которая решает задачу, с корректными базовыми случаями. (2) Определи состояние — аргументы которые полностью описывают подзадачу — и выбери кэш по нему (массив для маленьких целых, Map иначе). (3) Добавь три строки: проверь кэш и верни при попадании, вычисли при промахе, сохрани перед возвратом. (4) Сложность это отдельные-состояния x работа-на-состояние, плюс O(глубины) стек. Попробуй рецепт на подъёме по лестнице ниже, потом на подсчёте путей в сетке.
Объясни что это мемоизация, три шага внутри мемоизированной функции, почему она называется нисходящей, как выбрать структуру кэша, и её временную и пространственную сложность.
Мемоизация это нисходящий способ писать динамическое программирование: возьми естественную рекурсию и добавь кэш по состоянию подзадачи (её аргументам).
Три шага, по порядку:
- Проверь кэш — при попадании верни сохранённый ответ и пропусти всю работу.
- Вычисли при промахе — запусти обычный рекурсивный случай.
- Сохрани, потом верни — запиши ответ в кэш перед возвратом, так чтобы следующий вызов с теми же аргументами попал.
Нисходящий: начни от цели (fib(n)), спустись рекурсией к базовым случаям, заполни кэш на обратном пути вверх. Рекурсия обнаруживает какие подзадачи ей нужны. (Табуляция, следующий урок, это восходящая противоположность.)
Структура кэша: массив для состояний-маленьких-неотрицательных-целых (индексируй напрямую, используй сигнальное значение как undefined чтобы отметить “не вычислено”); Map для нецелых, разреженных или кортежных ключей.
Выигрыш: каждое отдельное состояние вычисляется раз, так что O(2^n) наивного Фибоначчи становится O(n) — fib(30) падает с 2,7 миллиона вызовов до 59.
Правило сложности: время = (отдельные состояния) x (работа на состояние). Память = кэш O(n) плюс стек рекурсии O(n) — этот стек это стоимость которую платит нисходящий и которую табуляция избегает.
Дальше: урок 03 реализует тот же DP восходящим способом с табуляцией — цикл который заполняет таблицу от базовых случаев вверх, без стека рекурсии, часто с O(1) памятью.