Какая разница между рекурсией, памятью и динамическим программированием?

Ответ 1

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

Чистая рекурсия:

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

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

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

Рекурсия с напоминанием /DP:

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;
}

Теперь у нас есть линейное количество вызовов в первый раз и постоянное значение после него.

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

Следующее также будет считаться DP, но без рекурсии:

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]; }

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

Также следующее не является ни рекурсией, ни DP:

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;
}

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

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

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

Ответ 2

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

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

Итак, правильнее сказать, что

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

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

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

Ответ 3

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

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

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

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

Ответ 4

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

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

Пример:

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

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

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

Ответ 5

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

В противном случае это дублированный вопрос: Динамическое программирование и memoization: снизу вверх и сверху вниз