В чем разница между рекурсией, мемоизацией и динамическим программированием?

Рассмотрим вычисление последовательности Фибоначчи:

Чистой воды рекурсию:

в

int fib(int x)
{
    if (x < 2)
        return 1;

    return fib(x-1) + fib(x-2);
}

результаты в экспоненциальное число звонков.

Рекурсия с мемоизацией/ДП:

int fib(int x)
{
    static vector<int> cache(N, -1);

    int& result = cache[x];

    if (result == -1)
    {
        if (x < 2)
            result = 1;
        else
            result = fib(x-1) + fib(x-2);
    }

    return result;
}

Теперь мы имеем линейное количество звонков в первый раз, и неизменными.

Описанный выше метод называется "ленивый" по. Мы рассчитываем на более ранние сроки в первый раз они просили.

Следующие будут также рассматриваться в ДП, но без рекурсии:

int fibresult[N];

void setup_fib()
{
    fibresult[0] = 1;
    fibresult[1] = 1;
    for (int i = 2; i < N; i++)
       fibresult[i] = fibresult[i-1] + fibresult[i-2];
}

int fib(int x) { return fibresult[x]; }

Этот способ может быть описан как "рвется" В, С "анимации" или "итерационный и". Его быстрее в целом, но мы должны вручную рисунок последовательность подзадач должны быть рассчитаны. Это очень просто для Фибоначчи, но для более сложных задач ДП это становится все труднее, и поэтому мы вернемся к ленивым рекурсивный метод, если это достаточно быстро.

Также не является ни рекурсии, ни ДП:

int fib(int x)
{
    int a = 1;
    int b = 1;
    for (int i = 2; i < x; i++)
    {
        a = a + b;
        swap(a,b);
    }
    return b;
}

Он использует постоянные пространстве и линейном времени.

Также я упомяну для полноты картины существует закрытая форма для Фибоначчи, который использует рекурсию пустоты, ни ДП, что позволяет рассчитывать на постоянный срок Фибоначчи, используя математические формулы, основанные на золотой пропорции:

http://www.dreamincode.net/forums/topic/115550-fibonacci-closed-form/

Ну, рекурсия+мемоизация - это как раз специфический "вкус" динамического программирования: динамическое программирование в соответствии с подходом сверху вниз.

Точнее, нет никакой необходимости использовать именно рекурсию. Любое решение типа "разделяй и властвуй" в сочетании с мемоизацией является динамическим программированием сверху вниз. (Рекурсия - это LIFO-способ разделения и покорения, в то время как вы также можете использовать FIFO-способ разделения и покорения или любой другой способ разделения и покорения).

Поэтому правильнее будет сказать, что

divide & conquer + memoization == top-down dynamic programming

Также, с очень формальной точки зрения, если вы реализуете решение "разделяй и властвуй" для задачи, которая не генерирует повторяющихся частичных решений (что означает, что нет никакой пользы от мемоизации), то вы можете утверждать, что это решение "разделяй и властвуй" является вырожденным примером "динамического программирования".

Однако динамическое программирование - это более общее понятие. Динамическое программирование может использовать подход "снизу вверх", что отличается от "разделяй и властвуй+памятование".

Я уверен, что вы можете найти подробное определение в интернете. Вот моя попытка упростить ситуацию.

Рекурсия снова дает о себе знать.

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

Мемоизация - это способ оптимизации алгоритмов ДП, которые полагаются на рекурсию. Смысл не в том, чтобы снова решать подпроблему, которая уже была решена. Можно рассматривать это как кэш решений подзадач.

Это разные понятия. Они довольно часто пересекаются, но они разные.

Рекурсия происходит, когда функция вызывает сама себя, прямо или косвенно. Это все.

Пример:

a -> call a
a -> call b, b -> call c, c -> call a

Динамическое программирование - при использовании решений меньших подзадач для решения более широкой проблемы. Это проще всего реализовать рекурсивно, потому что вы обычно думаем, что такие решения в терминах рекурсивных функций. Возможность поэтапного внедрения является предпочтительным, поскольку он занимает меньше времени и памяти.

Мемоизация используется для предотвращения рекурсивной реализации ДП, занимать гораздо больше времени, чем нужно. В большинстве случаев, алгоритм ДП будет использовать те же подзадачи решить несколько больших проблем. В рекурсивной реализации, это означает, что мы будем пересчитывать то же самое несколько раз. Мемоизация предполагает сохранение результатов этих подзадач в таблицу. При входе в рекурсивный вызов, мы проверяем, если его результат присутствует в таблице: если да, то вернуть его, если нет, то вычислить его, сохранить его в таблице, а затем вернуть его.

Рекурсия не имеет абсолютно никакого отношения к мемоизации и динамическому программированию; это совершенно отдельная концепция.

В противном случае, это дублирующий вопрос: https://stackoverflow.com/questions/6164629/dynamic-programming-and-memoization-top-down-vs-bottom-up-approaches.