Прежде чем я начну, нет, это не вопрос о том, в чем разница между мемоизацией и динамическим программированием или какой из них лучше, а просто простой вопрос о незначительной разнице между тем, как они обрабатывают кешированные поиски.
DP использует восходящий подход, в то время как мемоизация использует нисходящий. Таким образом, с DP вы начинаете с создания таблицы кэшированных вычислений, а затем передаете эти кэшированные значения более крупным вычислениям, чтобы избежать избыточных рекурсивных или итерационных вызовов функций. Мемоизация более или менее просто кэширует результат каждого вызова функции в хеш или массив (возможно, массив), а затем предоставляет результат в вызове функции (он просто пропускает все, что происходит в теле функции).
Мой вопрос в том, что я прав с тем, что я заявляю здесь? Оба подхода выглядят одинаково, только DP сложнее и немного эффективнее с памятью по сравнению с мемоизацией. С мемоизацией ваша программа по-прежнему должна запускать каждый вызов функции, даже если она кэширована, и каждый из этих вызовов функций может быстро заполнить стек, тогда как в DP она будет проверять таблицу массивов внутри функции и вызывать только рекурсивные функции. /итеративная функция, если она не найдена.
Я прав здесь? Или я что-то упускаю?
