Динамическое программирование
Стратегия динамического программирования:
Динамическое программирование и запоминание работают вместе. Основное различие между динамическим программированием и разделяй и властвуй заключается в том, что в случае последнего подзадачи независимы, тогда как в DP (динамическом программировании) подзадачи могут перекрываться. Используя мемоизацию [ведение таблицы уже решенных подзадач], динамическое программирование снижает экспоненциальную сложность до полиномиальной (O (n²), O (n³) и т. д.) для многих задач. Основными компонентами ДП являются:
-› Рекурсия: рекурсивно решает подзадачи.
-› Мемоизация: сохраняет уже вычисленные значения в таблице (мемоизация означает кэширование).
Динамическое программирование = рекурсия + мемоизация
Свойства стратегии динамического программирования:
Два свойства динамического программирования, которые могут сказать, может ли он решить данную проблему или нет:
-› Оптимальная подструктура: оптимальное решение проблемы содержит оптимальное решение подзадач.
-› Перекрывающиеся подзадачи: рекурсивное решение содержит небольшое количество отдельных подзадач, повторяющихся много раз.
ПРИМЕЧАНИЕ. Разница между DP и прямой рекурсией заключается в запоминании рекурсивных вызовов. Если подзадачи независимы и нет повторения, то мемоизация не помогает, поэтому динамическое программирование не является решением для всех задач.
Подходы к динамическому программированию:
В основном есть два подхода к решению задач DP:
-› Динамическое программирование снизу вверх
-› Динамическое программирование сверху вниз
Восходящее динамическое программирование:
В этом методе мы оцениваем функцию, начиная с наименьшего возможного значения входного аргумента, а затем переходим к возможным значениям, медленно увеличивая значение входного аргумента. При вычислении значений мы сохраняем все вычисленные значения в таблице (памяти). По мере оценки больших аргументов можно использовать предварительно вычисленные значения для меньших аргументов.
Динамическое программирование сверху вниз:
В этом методе проблема разбивается на подзадачи, каждая из этих подзадач решается, а решения запоминаются на случай, если их необходимо решить. Кроме того, мы сохраняем каждое вычисленное значение как последнее действие рекурсивной функции, а в качестве первого действия проверяем, существует ли предварительно вычисленное значение.
Пример ДП:
-> Серия Фибоначчи:
В ряду Фибоначчи текущее число представляет собой сумму двух предыдущих чисел. Ряд Фибоначчи определяется следующим образом:
Fib(n) = 0, для n = 0
= 1, для n = 1
= Fib(n-1) + Fib(n-2), для n > 1
-> Рекурсивная реализация может быть задана как:
int RecursiveFibonacci (int n) {
if(n == 0)
вернуть 0;
if(n == 1)
вернуть 1;
return RecursiveFibonacci(n — 1) + RecursiveFibonacci(n — 2);
}
-> Решение приведенного выше повторения дает:
T(n) = T(n — 1) + T(n — 2) + 1 ≈ (2^n) = O(2^n)
-› Чем помогает мемоизация?
Вызов f(4) создает дерево вызовов, которое многократно вызывает функцию для одного и того же значения:
В приведенном выше примере f(2) вычислялось два раза (перекрытие подзадач). Если n велико, то пересчитывается гораздо больше значений, что соответствует алгоритму экспоненциального времени. Вместо того, чтобы снова и снова решать одни и те же подзадачи, мы можем сохранить предыдущие вычисленные значения и уменьшить сложность. Здесь на сцену выходит мемоизация.
Теперь мы видим, как DP уменьшает сложность этой задачи с экспоненциальной до полиномиальной.
Как обсуждалось ранее, есть два способа сделать это. Один подход восходящий: эти методы начинают с более низких значений входных данных и продолжают строить решения для более высоких значений.
int фиб[n];
int fib(int n) {
// Проверяем базовые случаи
if(n == 0 || n == 1)
вернуть 1;
фиб[0] = 1;
фиб[1] = 1;
for(int i = 2; i ‹ n; i++) {
fib[i] = fib[i — 1] + fib[i — 2];
}
вернуть fib[n — 1];
}
Другой подход — сверху вниз. В этом методе мы сохраняем рекурсивные вызовы и используем значения, если они уже вычислены. Реализация для этого следующая:
int фиб[n];
int фибоначчи (int n) {
if(n == 1)
вернуть 1;
if(n == 2)
вернуть 1;
если (фиб[п] != 0)
вернуть фиб[n];
фиб [n] = фибоначчи [n — 1] + фибоначчи [n — 2];
}
ПРИМЕЧАНИЕ. Для всех проблем может оказаться невозможным найти решение как для нисходящего, так и для восходящего программирования.
Обе версии реализаций ряда Фибоначчи явно снижают сложность задачи до O(n). Это потому, что если значение уже вычислено, мы не вызываем подзадачи снова. Вместо этого мы напрямую берем его значение из таблицы.
Временная сложность: O(n). Пространственная сложность: O(n), для таблицы.
Дальнейшее улучшение: Еще одно наблюдение из ряда Фибоначчи: Текущее значение является суммой только двух предыдущих вычислений. Это указывает на то, что нам не нужно сохранять все предыдущие значения. Вместо этого, если мы сохраним только два последних значения, мы сможем вычислить текущее значение. Реализация для этого дается как:
int фибоначчи (int n) {
int a = 0, b = 1, сумма;
for(int i = 0; i ‹ n; i++) {
сумма = а + б;
a = b;
б = сумма;
}
сумма возврата;
}
Временная сложность: O(n). Космическая сложность: O(1).
ПРИМЕЧАНИЕ. Этот метод может не применяться (доступен) для всех проблем.
Наблюдения:
При решении задач с помощью DP попытайтесь выяснить следующее:
-› Посмотрите, как проблемы рекурсивно определяются с точки зрения подзадач.
-› Посмотрим, можем ли мы использовать какую-нибудь таблицу [запоминание], чтобы избежать повторных вычислений.
