Может ли рекурсия быть динамическим программированием?

Question

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

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

Например. Для Фибоначчи, я могу иметь рекурсивный алгоритм:

RecursiveFibonacci(n) 
if (n=1 or n=2) 
    return 1 
else 
    return RecursiveFibonacci(n-1) + RecursiveFibonacci(n-2) 

В этой ситуации, одни и те же подзадачи могут быть решены над- и-снова. Это делает это не динамическое программирование? То есть, если бы я хотел динамического программирования, я бы должен был избежать разрешения подзадач, например, используя массив длины n и хранить решение для каждой подзадачи (первые индексы массива: 1, 1, 2, 3, 5, 8, 13, 21)?

Fibonacci(n) 
F1 = 1 
F2 = 1 
for i=3 to n 
    Fi=Fi-1 + Fi-2 
return Fn 

Answer 1

Динамические программы обычно могут быть кратко описаны с помощью рекурсивных формул.

Но если вы реализуете их с помощью простых рекурсивных компьютерных программ, они часто неэффективны именно по той причине, которую вы поднимаете: повторяется то же вычисление. Фибоначчи - пример повторных вычислений, хотя это не динамическая программа.

Существует два подхода, позволяющих избежать повторения.

1. Memoization. Идея здесь заключается в том, чтобы кэшировать ответ, рассчитанный для каждого набора аргументов, на рекурсивную функцию и возвращать кешированное значение, когда оно существует.

2. Нижняя таблица. Здесь вы «разматываете» рекурсию, чтобы результаты на уровнях, меньших, чем я, были объединены с результатом на уровне i. Обычно это изображается как заполнение таблицы, где уровни - это строки.

Один из этих методов подразумевается для любого алгоритма DP. Если вычисления повторяются, алгоритм не является DP. Поэтому ответ на ваш вопрос «да».

Итак, пример ... Давайте попробуем проблему смены цен, если у вас есть монеты со значениями v_1, v_2, ... v_n, используя минимальное количество монет.

Пусть N (c) - минимальное количество монет, необходимых для создания центов. Тогда рекурсивная формулировка

N(c) = 1 + min_{i = 1..n} N(c - v_i) 

Базовые случаи N (0) = 0 и N (K) = инф для к < 0.

Для memoize этого требуется только отображение хэш-таблица C до N (с).

В этом случае «таблица» имеет только одно измерение, которое легко заполнить. Скажем, мы имеем монеты со значениями 1, 3, 5, то таблица N начинается с

• N (0) = 0, начальное условие.
• N (1) = 1 + min (N (1-1), N (1-3), N (1-5) = 1 + min (0, inf, inf) = 1
• N (2) = 1 + мин (N (2-1), N (2-3), N (2-5) = 1 + мин (1, inf, inf) = 2
• N (3) = 1 + min (N (3-1), N (3-3), N (3-5) = 1 + min (2, 0, inf) = 1

Вы получаете идею. Вы всегда можете вычислить N (c) из N (d), d < c.

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

Таблица k-мерная для k независимых переменных в рекурсивном выражении.