Как программа узнаёт знакомую задачу
Мемоизация — это способ ускорить программу, сохраняя ответы на уже выполненные вычисления. Обычно их складывают в таблицу: входные данные служат ключом, а полученный результат — значением. Когда программа встречает тот же вход снова, она проверяет таблицу и сразу возвращает сохранённый ответ.
Представьте функцию, которая снова и снова вычисляет стоимость доставки для одного и того же набора адресов и параметров. Без запоминания она каждый раз проделывает расчёт заново. С мемоизацией повторный запрос превращается в поиск готовой записи. Первый вызов может быть таким же долгим, зато последующие обходятся дешевле.
Почему это особенно полезно для рекурсивных вычислений
При рекурсии функция решает задачу, вызывая саму себя для более простых частей. Эти части иногда повторяются. Например, при вычислении числа Фибоначчи для `n` программа сводит задачу к значениям для `n−1` и `n−2`, а затем снова запрашивает одни и те же числа на разных ветвях. Без сохранения промежуточных ответов число вызовов быстро растёт; с мемоизацией каждое нужное значение вычисляется один раз и затем переиспользуется.
Такой приём не меняет сам ответ и обычно не требует придумывать новый алгоритм. Он меняет то, сколько работы программа повторяет: вместо множества одинаковых вычислений остаётся вычисление каждой уникальной подзадачи и обращение к таблице.
Ускорение требует памяти
Таблица занимает место, а поиск и запись тоже имеют стоимость. Поэтому мемоизация выгодна, когда повторов достаточно много и сохранённые результаты помещаются в доступную память. Если входы почти никогда не повторяются или каждый результат занимает много места, таблица может дать мало пользы.
Иными словами, программа обменивает часть памяти на меньшее число вычислений. Именно поэтому задача, которая в рекурсивном варианте разрасталась из-за повторов, иногда становится быстрой после одного изменения: не считать знакомое заново, а сохранить его ответ.
