← Все вопросы
Что такое динамическое программирование? Фибоначчи с мемоизацией
17
Все пугают «динамическим программированием». Звучит страшно. Можете показать суть на Фибоначчи — почему обычная рекурсия медленная и как мемоизация её ускоряет?
3 ответа
28
✓ Принятый ответ — помог автору
Суть динамики проще, чем название: если задача распадается на одинаковые подзадачи, которые ты считаешь по многу раз — посчитай каждую ОДИН раз и запомни ответ. Это и есть мемоизация.
Наивный Фибоначчи пересчитывает одни и те же значения экспоненциально много раз:
def fib(n):
if n < 2:
return n
return fib(n - 1) + fib(n - 2)
# fib(40) уже считается заметно долго
Добавляем кеш — и сложность падает с O(2^n) до O(n):
from functools import lru_cache
@lru_cache(maxsize=None)
def fib(n):
if n < 2:
return n
return fib(n - 1) + fib(n - 2)
# fib(100) — мгновенно
Вот и весь фокус: «запоминай уже посчитанное». Дальше идёт вариант снизу-вверх (таблицей), но идея та же.
Ivan Ivanov @да, memo = {}; if n in memo: return memo[n] и т.д. · 17 месяцев назад
Евгений Костенко lru_cache одной строкой — магия 😄 · 17 месяцев назад
Алиса Сергеева а без декоратора как? через словарь руками? · 17 месяцев назад
12
Снизу-вверх без рекурсии вообще, O(n) времени и O(1) памяти:
def fib(n):
a, b = 0, 1
for _ in range(n):
a, b = b, a + b
return a
Для Фибоначчи это самый практичный вариант.
6
ДП = «разбей на подзадачи + не считай дважды». Всё.
Ваш ответ
Войдите, чтобы ответить на вопрос.
