Мемоизация: сверху вниз

Зачем нужно ДП

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

Классический пример боли — наивные числа Фибоначчи. fib(n) = fib(n-1) + fib(n-2) пересчитывает одни и те же значения снова и снова, и для n=40 уже заметно тормозит. Посмотрим, почему.

Мемоизация (top-down)

Мемоизация — это «ДП сверху вниз»: оставляем привычную рекурсиюПриём, при котором функция вызывает саму себя. Нужен базовый случай, чтобы вызовы завершились., но заводим кэш (словарьКоллекция пар «ключ → значение»: {"a": 1}. Быстрый доступ по ключу. По-английски dict.). Перед вычислением проверяем: если ответ для n уже посчитан — возвращаем готовый. Так каждая подзадача решается ровно один раз.

Вернётся 5. Способы для 4 ступеней: 1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2. Чтобы попасть на ступень n, мы пришли либо с (n-1) шагом в 1, либо с (n-2) шагом в 2 — отсюда сумма двух предыдущих.

⚠️ Частые ошибки новичков

Ошибка. Сделать memo аргументом по умолчанию в виде memo={}. Мутабельное значение по умолчанию создаётся один раз и сохраняется между вызовами — кэш «протечёт» из одного вызова в другой и даст неверные результаты при разных задачах. Правильно: memo=None и создавать словарь внутри. Запустите пример с протекающим кэшем.