Мемоизация и табуляция
Два способа кэшировать ответы для подзадач
«Мемоизация и табуляция» — бесплатный урок Competitive Programming Academy на CoddyKit. Это урок 1 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения Competitive Programming Academy, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс Competitive Programming Academy содержит 4 уроков всего.
Зачем вообще кэшировать
Наивная рекурсия снова и снова выполняет одну и ту же работу. Динамическое программирование сохраняет каждый ответ один раз, поэтому пересчитывать его не приходится.
fib(40) # slow: recomputes endlesslyПерекрывающиеся подзадачи
DP применяют, когда задача распадается на перекрывающиеся подзадачи. Один и тот же меньший случай встречается во многих ветвях рекурсии.
fib(5) needs fib(3) twiceСверху вниз: мемоизация
Мемоизация — это обычная рекурсия с кэшем. Вы вычисляете результат по мере необходимости и запоминаете его при первом обращении к каждому входному значению.
memo = {}Простая мемоизация в Python
Декоратор lru_cache превращает медленную рекурсию в быстрое DP одной строкой и автоматически кэширует каждый вызов.
from functools import lru_cache
@lru_cache(None)
def f(n): ...Снизу вверх: табуляция
Табуляция заполняет таблицу от самых маленьких случаев к ответу, используя цикл вместо рекурсии.
dp = [0] * (n + 1)Табличный ряд Фибоначчи
Задайте базовые значения, а затем позвольте каждой ячейке считывать значения, которые уже вычислены. Стек вызовов не нужен — только простой цикл.
dp[0], dp[1] = 0, 1
for i in range(2, n+1):
dp[i] = dp[i-1] + dp[i-2]Один ответ, разные подходы
Мемоизация и табуляция решают одно и то же рекуррентное соотношение. Различается только направление: сверху вниз по мере необходимости или снизу вверх по порядку.
Когда предпочесть мемоизацию
Выбирайте мемоизацию, когда рекуррентное соотношение естественно записывается рекурсивно и Вам может не понадобиться каждое состояние.
Когда предпочесть табуляцию
Выбирайте табуляцию для плотных циклов, чтобы избежать ошибок, связанных с лимитом рекурсии, и когда всё равно нужно вычислить всю таблицу.
import sys; sys.setrecursionlimit(10**6)Следите за лимитом рекурсии
Глубокая рекурсия с мемоизацией может достичь лимита рекурсии Python и завершиться с вердиктом «ошибка времени выполнения» на больших входных данных.
У обоих подходов одна общая выгода
В обоих случаях ускорение достигается за счёт того, что каждое состояние решается один раз. Общее время равно числу состояний, умноженному на работу для одного состояния.
Быстрая проверка
Какой подход заполняет таблицу снизу вверх с помощью цикла?
Повторение: два пути к одному DP
Теперь Вы умеете кэшировать подзадачи двумя способами. Мемоизация выполняет рекурсию сверху вниз, а табуляция — цикл снизу вверх. Выбирайте тот подход, который проще читать. ✨
Часто задаваемые вопросы
Урок «Мемоизация и табуляция» бесплатный?
Да — полный текст урока «Мемоизация и табуляция» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс Competitive Programming Academy, подпишись на CoddyKit PRO. Курс Competitive Programming Academy содержит 4 уроков всего.
Чему я научусь в уроке «Мемоизация и табуляция»?
Два способа кэшировать ответы для подзадач Ты практикуешь Competitive Programming Academy с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.
Нужен ли мне опыт, чтобы начать Competitive Programming Academy?
Предыдущий опыт не требуется. Competitive Programming Academy на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 1 из 4.
Сколько времени занимает урок «Мемоизация и табуляция»?
Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.
Можно ли писать и запускать код в этом уроке Competitive Programming Academy?
Да. Каждый урок Competitive Programming Academy включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.
Все уроки этого курса
- Мемоизация и табуляция
- Определение состояния и перехода
- Лестница и сочетания монет
- Наибольшая возрастающая подпоследовательность