Чем мемоизация отличается от табуляции в динамическом программировании?
В ДП постоянно встречаю два подхода: «сверху вниз с мемоизацией» и «снизу вверх с таблицей». В чём принципиальная разница, и какой выбирать?
3 ответа
Это два способа реализовать одно и то же ДП:
Мемоизация (top-down) — обычная рекурсия + кэш уже посчитанных значений. Пишешь как естественную рекурсию, считаешь только нужные подзадачи.
Табуляция (bottom-up) — заводишь массив и заполняешь его в цикле от базовых случаев к ответу. Никакой рекурсии.
# мемоизация
from functools import lru_cache
@lru_cache(None)
def fib_memo(n):
if n < 2: return n
return fib_memo(n-1) + fib_memo(n-2)
# табуляция
def fib_tab(n):
dp = [0, 1]
for i in range(2, n+1):
dp.append(dp[i-1] + dp[i-2])
return dp[n]
Когда что: мемоизация удобнее писать (просто навешиваешь кэш на рекурсию) и хороша, если нужны не все состояния. Табуляция не упирается в лимит рекурсии и обычно чуть быстрее по константе, плюс легче ужать память. Результат у обоих одинаковый.
Мемоизация — рекурсия с кэшем (сверху вниз). Табуляция — цикл, заполняющий таблицу (снизу вверх). Сложность та же.
Одно и то же ДП.
