Код Junior Динамическое программирование обновлено
Числа Фибоначчи с мемоизацией
Условие
fib(0)=0, fib(1)=1. Должно работать для n=50 мгновенно.
Примеры
fib(10) // 55
fib(0) // 0
fib(1) // 1
Как подойти
Мемоизация превращает O(2^n) в O(n). Дефолтный параметр memo = new Map() создаётся один раз на верхний вызов и передаётся дальше - если забыть передать, кэш бесполезен. Итеративный вариант с двумя переменными даёт O(1) памяти.
Подсказки: 2
- Без кэша сложность экспоненциальная.
- Кэш нужно передавать в рекурсивные вызовы, а не создавать заново.
Решите в тренажёре
Редактор с автотестами прямо в браузере. Можно решить спокойно, вслух или под таймером, как на собесе.