Мемоизация: кэширование результатов рекурсии
Применяйте @functools.lru_cache и словари ручной мемоизации к задачам о Фибоначчи и подъёме по ступенькам, устраняя экспоненциальные повторные вычисления
«Мемоизация: кэширование результатов рекурсии» — бесплатный урок DSA Interview Prep на CoddyKit. Это урок 4 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения DSA Interview Prep, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс DSA Interview Prep содержит 4 уроков всего.
Проблема избыточной рекурсии
Наивная рекурсивная реализация Фибоначчи многократно вычисляет одни и те же значения. fib(5) вызывает fib(4) и fib(3); fib(4) вызывает fib(3) и fib(2) — поэтому fib(3) вычисляется дважды. Эта избыточность растёт экспоненциально: fib(40) выполняет более миллиарда вызовов функций. Мемоизация решает проблему, сохраняя каждый результат при первом вычислении, чтобы последующие вызовы получали его за O(1), а не вычисляли заново.
# Count calls without memoisation
call_count = [0]
def fib_plain(n):
call_count[0] += 1
if n <= 1: return n
return fib_plain(n-1) + fib_plain(n-2)
fib_plain(20)
print(f'fib(20) without memo: {call_count[0]:,} calls')
# ~21,891 calls for n=20; ~1 billion for n=40Ручная мемоизация со словарём
Добавьте словарь memo в качестве параметра (или используйте замыкание). Перед вычислением проверьте, есть ли ответ в memo. Если есть, немедленно верните его. Если нет, вычислите ответ, сохраните его в memo и верните. Теперь каждая уникальная подзадача вычисляется ровно один раз, что преобразует O(2^n) времени в O(n) и требует O(n) памяти для словаря memo плюс O(n) памяти стека.
def fib_memo(n, memo={}):
if n in memo:
return memo[n]
if n <= 1:
return n
memo[n] = fib_memo(n-1, memo) + fib_memo(n-2, memo)
return memo[n]
print(fib_memo(10)) # 55
print(fib_memo(50)) # 12586269025
print(fib_memo(100)) # huge number — still fast!Декоратор functools.lru_cache
Python предоставляет @functools.lru_cache(maxsize=None) (также доступный как @functools.cache в Python 3.9 и более новых версиях) для автоматизации мемоизации. Добавление этого декоратора перед функцией кэширует все вызовы по их аргументам. maxsize=None означает неограниченный размер кэша — кэшируется каждая уникальная комбинация аргументов. Так любую рекурсивную функцию можно превратить в мемоизированную, добавив одну строку кода.
import functools
@functools.lru_cache(maxsize=None)
def fib(n):
if n <= 1:
return n
return fib(n-1) + fib(n-2)
print(fib(50)) # 12586269025
print(fib(100)) # 354224848179261915075
print(fib.cache_info()) # CacheInfo(hits=..., misses=..., maxsize=None, currsize=...)Подъём по лестнице (LeetCode 70)
LeetCode 70 «Подъём по лестнице»: Вы можете подниматься на 1 или 2 ступеньки за раз. Сколько существует способов достичь ступеньки n? Это замаскированная задача на числа Фибоначчи: ways(n) = ways(n-1) + ways(n-2). Базовые случаи: ways(0) = 1 (один способ остаться у основания), ways(1) = 1. С мемоизацией решение выполняется за O(n) времени и использует O(n) памяти.
import functools
@functools.lru_cache(maxsize=None)
def climbStairs(n):
if n <= 1:
return 1
return climbStairs(n-1) + climbStairs(n-2)
for i in range(1, 8):
print(f'climbStairs({i}) = {climbStairs(i)}')
# 1,2,3,5,8,13,21Размен монет (LeetCode 322)
LeetCode 322 «Размен монет»: даны номиналы монет и целевая сумма; найдите минимальное количество монет. Мемоизированная рекурсия сверху вниз: dp(amount) = 1 + min(dp(amount - coin)) для каждой допустимой монеты. Базовый случай: dp(0) = 0. Кэшируйте каждую промежуточную сумму. Если некоторую сумму невозможно составить, верните бесконечность. Мемоизация преобразует экспоненциальный полный перебор в решение со временем O(amount × len(coins)).
import functools
def coinChange(coins, amount):
@functools.lru_cache(maxsize=None)
def dp(rem):
if rem == 0:
return 0
if rem < 0:
return float('inf')
return 1 + min(dp(rem - c) for c in coins)
result = dp(amount)
return result if result != float('inf') else -1
print(coinChange([1, 5, 11], 15)) # 3 (5+5+5)
print(coinChange([1, 2, 5], 11)) # 3 (5+5+1)
print(coinChange([2], 3)) # -1Разбиение строки на слова (LeetCode 139) с мемоизацией
LeetCode 139 «Разбиение слов»: определите, можно ли разбить строку на слова из словаря. Рекурсия сверху вниз: can_break(s, start) перебирает все префиксы s[start:end]; если префикс есть в словаре и can_break(s, end) возвращает true, верните true. Без мемоизации решение выполняется за O(2^n); с мемоизацией (кэшированием каждого начального индекса) — за O(n² × L), где L — максимальная длина слова.
import functools
def wordBreak(s, wordDict):
word_set = set(wordDict)
@functools.lru_cache(maxsize=None)
def can_break(start):
if start == len(s):
return True
for end in range(start + 1, len(s) + 1):
if s[start:end] in word_set and can_break(end):
return True
return False
return can_break(0)
print(wordBreak('leetcode', ['leet', 'code'])) # True
print(wordBreak('applepenapple', ['apple','pen'])) # True
print(wordBreak('catsandog', ['cats','dog','sand','and','cat'])) # FalseМемоизация и табуляция
Мемоизация (сверху вниз) начинает с исходной задачи и кэширует ответы по мере их рекурсивного получения. Решаются только фактически необходимые подзадачи. Табуляция (снизу вверх) заранее заполняет таблицу, переходя от маленьких подзадач к большим, и решает все подзадачи независимо от необходимости. Мемоизацию проще вывести из рекурсивного решения; табуляция устраняет ограничения глубины рекурсии и накладные расходы на вызовы функций.
# Memoisation (top-down)
import functools
@functools.lru_cache(maxsize=None)
def fib_td(n):
if n <= 1: return n
return fib_td(n-1) + fib_td(n-2)
# Tabulation (bottom-up)
def fib_bu(n):
if n <= 1: return n
dp = [0] * (n + 1)
dp[1] = 1
for i in range(2, n + 1):
dp[i] = dp[i-1] + dp[i-2]
return dp[n]
print(fib_td(20), fib_bu(20)) # 6765 6765
# Both O(n) time; fib_bu avoids recursion limitОптимизация памяти: переменные с обновлением
Многие задачи DP, которые мемоизированная рекурсия решает с использованием O(n) памяти, можно дополнительно оптимизировать до O(1) памяти, если нужны ответы лишь для фиксированного числа предыдущих подзадач. Для Фибоначчи важны только два последних значения. То же верно для подъёма по лестнице. Две последовательно обновляемые переменные заменяют весь словарь memo или таблицу.
# Fibonacci with O(1) space
def fib_o1(n):
if n <= 1:
return n
prev2, prev1 = 0, 1
for _ in range(2, n + 1):
prev2, prev1 = prev1, prev2 + prev1
return prev1
for i in range(8):
print(f'fib({i})={fib_o1(i)}', end=' ')
print()
# Climbing stairs O(1) space
def climbStairs_o1(n):
if n <= 1: return 1
a, b = 1, 1
for _ in range(2, n + 1):
a, b = b, a + b
return b
print(climbStairs_o1(10)) # 89lru_cache и замыкание и глобальный словарь
Существует три способа реализовать мемоизацию вручную. Глобальный словарь прост, но загрязняет область видимости модуля. Замыкание инкапсулирует кэш внутри функции, предотвращая утечку состояния, но требует обёртки. @lru_cache — самый лаконичный вариант: один декоратор заменяет весь шаблонный код. На собеседовании начинайте с @lru_cache, если только интервьюер специально не попросит ручную реализацию.
import functools
# 1. Global dict (messy)
memo_global = {}
def fib_global(n):
if n in memo_global: return memo_global[n]
if n <= 1: return n
memo_global[n] = fib_global(n-1) + fib_global(n-2)
return memo_global[n]
# 2. Closure (cleaner scope)
def make_fib():
cache = {}
def fib(n):
if n in cache: return cache[n]
if n <= 1: return n
cache[n] = fib(n-1) + fib(n-2)
return cache[n]
return fib
fib_closure = make_fib()
# 3. lru_cache (best)
@functools.lru_cache(maxsize=None)
def fib_cached(n):
if n <= 1: return n
return fib_cached(n-1) + fib_cached(n-2)
print(fib_global(30), fib_closure(30), fib_cached(30)) # all 832040Когда мемоизация не помогает
Мемоизация ускоряет только задачи с перекрывающимися подзадачами — случаи, когда одна и та же подзадача вычисляется несколько раз. Если каждая подзадача уникальна (например, при простом обходе дерева, где каждый узел посещается ровно один раз), мемоизация добавляет накладные расходы, но не даёт преимуществ. Кроме того, мемоизация не может исправить задачи, в которых дерево рекурсии экспоненциально по числу различных подзадач, а не из-за повторного использования — для них требуется совершенно другой алгоритм.
# Memoisation DOES help: overlapping sub-problems (Fibonacci)
# fib(n) reuses fib(n-2), fib(n-3), etc.
# Memoisation does NOT help: distinct sub-problems (permutations)
# Each unique (remaining_elements, target) pair is truly distinct
# The exponential complexity comes from the state space itself
print('Memoisation: useful when SAME sub-problem recurs multiple times')
print('Not useful: when every sub-problem is unique to one recursive path')Итоги: список проверок для мемоизации
Применяйте мемоизацию, когда: у Вас есть корректное, но медленное рекурсивное решение из-за повторных вычислений; функция имеет небольшое число различных комбинаций аргументов; а возвращаемое значение зависит только от аргументов (чистая функция — без побочных эффектов и глобального состояния). Проверьте пространство состояний подзадач: если существует не более O(n) или O(n²) различных состояний, мемоизация преобразует экспоненциальное время в полиномиальное.
Быстрая проверка
Проверьте своё понимание концепций курса «Структуры данных и алгоритмы — подготовка к собеседованию по программированию» из этого урока.
Повторение урока
В этом уроке Вы узнали: мемоизация сохраняет результаты подзадач, чтобы избежать повторных вычислений и преобразовать экспоненциальную рекурсию в полиномиальное время, @functools.lru_cache — идиоматичный инструмент Python, для использования которого нужна всего одна строка, а также мемоизация (сверху вниз) и табуляция (снизу вверх) — два стиля DP: мемоизацию проще вывести, а табуляция устраняет проблемы с глубиной стека. Поздравляем — Вы завершили модули по рекурсии и хеш-таблицам!
Часто задаваемые вопросы
Урок «Мемоизация: кэширование результатов рекурсии» бесплатный?
Да — полный текст урока «Мемоизация: кэширование результатов рекурсии» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс DSA Interview Prep, подпишись на CoddyKit PRO. Курс DSA Interview Prep содержит 4 уроков всего.
Чему я научусь в уроке «Мемоизация: кэширование результатов рекурсии»?
Применяйте @functools.lru_cache и словари ручной мемоизации к задачам о Фибоначчи и подъёме по ступенькам, устраняя экспоненциальные повторные вычисления Ты практикуешь DSA Interview Prep с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.
Нужен ли мне опыт, чтобы начать DSA Interview Prep?
Предыдущий опыт не требуется. DSA Interview Prep на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 4 из 4.
Сколько времени занимает урок «Мемоизация: кэширование результатов рекурсии»?
Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.
Можно ли писать и запускать код в этом уроке DSA Interview Prep?
Да. Каждый урок DSA Interview Prep включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.
Все уроки этого курса
- Структура рекурсии: базовый случай, доверие, построение
- Визуализация стека вызовов
- Компромиссы рекурсивного и итеративного подходов
- Мемоизация: кэширование результатов рекурсии