Рекурсия + мемоизация =? Динамическое программирование

По сути мемоизация и динамическое программирование - это приёмы оптимизации рекурсивного подхода. Обычно они оба оптимизируют одинаково эффективно. Но это всё-таки разные вещи.

Нет. Иногда посредством рекурсии и мемоизации можно решать задачи динамического программирования, однако динамическое программирование в общем случае - это способ решения оптимизационных задач, в которых явным образом выделяемы этапы (во времени, в размерности задачи и т. п.). При этом подразумевается последовательная оптимизация каждого из этапов (см. функциональные уравнения Беллмана) до тех пор, пока не будет найдено оптимальное решение исходной задачи.

И «рекурсивное решение с мемоизацией», и «переписывание для решения снизу вверх» являются лишь способами реализации. То есть и так, и этак вы можете решать задачу методом динамического программирования.

+1024 причем исходная оптимизационная задача обобщается, и решается уже более общая задача. Теория оптимизации. Другое название - математическое программирование.

Важная составляющая задач, решающихся методом динамического программирования — то, что подзадачи пересекаются. В определении «рекурсия + мемоизация» явно об этом не говорится. Тем более это не учитывается в способе, когда задача переписывается для решения снизу вверх. Что касается алгоритмов, то в последнем случае к ним отнесутся и классические задачи с решением по методу «разделяй и властвуй»; тут же можно добавить, что задачи динамического программирования могут решаться и «сверху вниз».

Я просто неправильно поставил вопрос. Изучив различные источники стало понятно что рекурсия+мемоизация, это просто способо реализации метода, а не сам метод. В данном вопросе я отнес методы решения задач, и методы реализации к одной области, чего делать не следовало.

Динамическое программирование допустимо реализовывать при помощи рекурсии с мемоизацией.

Спасибо, вопрос закрыт.