Динамическое программирование (DP) - это простой метод, но его сложно освоить. Один из простых способов выявить и решить проблемы DP - решить как можно больше проблем. Термин «программирование» не имеет отношения к кодированию, но взят из литературы и означает заполнение таблиц (аналогично линейному программированию).
Динамическое программирование и запоминание работают вместе. Основное различие между динамическим программированием и «разделяй и властвуй» состоит в том, что в последнем случае подзадачи независимы, тогда как в DP подзадачи могут накладываться друг на друга. Используя запоминание [ведение таблицы уже решенных подзадач], динамическое программирование снижает экспоненциальную сложность до полиномиальной сложности (O (n2), O (n3) и т. Д.) Для многих задач.
Основными компонентами DP являются:
- Рекурсия: рекурсивно решает подзадачи.
- Запоминание: сохраняет уже вычисленные значения в таблице (запоминание означает кеширование).
Dynamic Programming = Recursion + Memorization
Свойства динамического программирования-
Два свойства динамического программирования, которые могут сказать, может ли оно решить данную проблему или нет:
- Оптимальная подструктура: оптимальное решение проблемы содержит оптимальные решения подзадач.
- Перекрывающиеся подзадачи: рекурсивное решение содержит небольшое количество отдельных подзадач, повторяющихся много раз.
ПРИМЕЧАНИЕ. Подобно техникам «Жадность» и «Разделяй и властвуй», DP не может решить все проблемы. Есть проблемы, которые нельзя решить никакими алгоритмическими методами [жадное, разделяй и властвуй и динамическое программирование].
Разница между динамическим программированием и простой рекурсией заключается в запоминании рекурсивных вызовов. Если подзадачи независимы и нет повторения, запоминание не помогает, поэтому динамическое программирование не является решением всех проблем.
Подходы к динамическому программированию-
В основном есть два подхода к решению задач DP:
- Восходящее динамическое программирование
- Нисходящее динамическое программирование
восходящее динамическое программирование:
В этом методе мы оцениваем функцию, начиная с наименьшего возможного значения входного аргумента, а затем перебираем возможные значения, медленно увеличивая значение входного аргумента. При вычислении значений мы сохраняем все вычисленные значения в таблице (памяти). По мере оценки более крупных аргументов могут использоваться предварительно вычисленные значения для меньших аргументов.
Нисходящее динамическое программирование:
В этом методе проблема разбита на подзадачи; каждая из этих подзадач решена; и запомнили решения на случай, если их нужно будет решить. Кроме того, мы сохраняем каждое вычисленное значение как последнее действие рекурсивной функции и в качестве первого действия проверяем, существует ли предварительно вычисленное значение.
Программирование снизу вверх и сверху вниз -
В восходящем программировании программист должен выбрать значения для расчета и определить порядок расчета. В этом случае все подзадачи, которые могут потребоваться, решаются заранее, а затем используются для построения решений более крупных проблем. При программировании сверху вниз рекурсивная структура исходного кода сохраняется, но избегается ненужный пересчет. Проблема разбита на подзадачи, эти подзадачи решаются, а решения запоминаются на тот случай, если их нужно будет решить снова.
Примеры алгоритмов динамического программирования-
- Многие строковые алгоритмы, включая самую длинную общую подпоследовательность, самую длинную возрастающую подпоследовательность, самую длинную общую подстроку, расстояние редактирования.
- Алгоритмы на графах могут быть решены эффективно: алгоритм Беллмана-Форда для поиска кратчайшего расстояния в графе, алгоритм кратчайшего пути Флойда All-Pairs и т. Д.
- Цепное умножение матриц
- Сумма подмножества
- 0/1 Рюкзак
- Задача коммивояжера и многое другое
Пример:
1. Ряд Фибоначчи-
В рядах Фибоначчи текущее число - это сумма двух предыдущих чисел. Ряд Фибоначчи определяется следующим образом:
Fib(n) = 0 ------------------------> for n=0
= 1 ------------------------> for n=1
= Fib(n-1) + Fib(n-2) -----> for n > 1
Рекурсивная реализация может быть представлена как:
int RecursiveFib (int n)
{
if(n == 0) return 0;
if (n ==1 ) return 1;
return RecursiveFib (n - 1) + RecursiveFib (n - 2);
}
Чем помогает запоминание?
Вызов fib (5) создает дерево вызовов, которое вызывает функцию с одним и тем же значением много раз:
фиб (5)
фиб (4) + фиб (3)
(фиб (3) + фиб (2)) + (фиб (2) + фиб (1))
((фиб (2) + фиб (1)) + (фиб (1) + фиб (0))) + ((фиб (1) + фиб (0)) + фиб (1))
(((фиб (1) + фиб (0)) + фиб (1)) + (фиб (1) + фиб (0))) + ((фиб (1) + фиб (0)) + фиб (1) )
В приведенном выше примере fib (2) вычислялся трижды (перекрытие подзадач). Если n большое, то пересчитывается гораздо больше значений fib (подзадач), что приводит к алгоритму экспоненциального времени. Вместо того, чтобы решать одни и те же подзадачи снова и снова, мы можем сохранить предыдущие вычисленные значения и уменьшить сложность.
Запоминание работает следующим образом: начните с рекурсивной функции и добавьте таблицу, которая сопоставляет значения параметров функции с результатами, вычисленными функцией. Затем, если эта функция вызывается дважды с одними и теми же параметрами, мы просто ищем ответ в таблице.
Улучшение: теперь мы видим, как DP снижает сложность этой задачи с экспоненциальной до полиномиальной. Как обсуждалось ранее, это можно сделать двумя способами. Один из подходов - восходящий: эти методы начинают с более низких значений входных данных и продолжают строить решения для более высоких значений.
int fib[n];
int fib (int n)
{
//Checking base cases
if (n ==0 || n == 1) return 1;
fib[0] = 1;
fib[1] = 1;
for (int i=2 ; i <n ; i++)
fib[i] = fib[i-1] + fib[i-2];
return fib[n-1];
}
Другой подход - сверху вниз. В этом методе мы сохраняем рекурсивные вызовы и используем значения, если они уже вычислены. Реализация для этого представлена как:
int fib[n];
int fibonacci (int n)
{
if (n == 1)
return 1;
if (n == 1)
return 1;
if (fib[n] != 0)
return fib[n];
return fib[n] = fibonacci (n-1) + fibonacci (n-2);
}
Примечание. Для всех проблем может оказаться невозможным найти решения программирования как сверху вниз, так и снизу вверх.
Обе версии реализаций ряда Фибоначчи явно снижают сложность задачи до O (n). Это потому, что если значение уже вычислено, мы больше не вызываем подзадачи. Вместо этого мы напрямую берем его значение из таблицы.
Сложность времени: O (n).
Сложность пространства: O (n), для таблицы.
Дальнейшее улучшение: Еще одно наблюдение из ряда Фибоначчи: текущее значение - это сумма только двух предыдущих вычислений. Это означает, что нам не нужно сохранять все предыдущие значения. Вместо этого, если мы сохраним только два последних значения, мы сможем вычислить текущее значение.
Реализация для этого приведена ниже:
int fibonacci (int n)
{
int a = 0 , b = 1 , sum , i;
for (i = 2 ; i < n ; i++) {
sum = a+b;
a = b;
b = sum;
}
return sum;
}
Сложность времени: O (n).
Сложность пространства: O (1).
Примечание. Этот метод может быть применим (доступен) не для всех проблем.
Наблюдения- Решая проблемы с помощью DP, постарайтесь выяснить следующее:
- Посмотрите, как рекурсивно определяются проблемы в терминах подзадач.
- Посмотрим, можем ли мы использовать какую-нибудь таблицу [запоминание], чтобы избежать повторных вычислений.
