Разъяснение с примерами. Просто взгляните и дайте мне знать, что думаете по этому поводу!
Обзор
Динамическое программирование и мемоизация работают вместе. Основное различие между динамическим программированием и разделяй и властвуй состоит в том, что в последнем случае подзадачи независимы, тогда как в DP можно быть перекрытием подзадач.
Используя мемоизацию [ведение таблицы подзадач, уже решенных], динамическое программирование снижает экспоненциальную сложность до полиномиальной сложности (O (n 2) , O (n 3) и т. Д.) Для многих задач.
Компоненты динамического программирования
Обычно динамическое программирование состоит из двух компонентов:
Dynamic Programming = Recursion + Memoization
Свойства стратегии динамического программирования
Два свойства динамического программирования, которые могут сказать, может ли оно решить данную проблему или нет:
- Оптимальная подструктура: оптимальное решение проблемы содержит оптимальные решения подзадач.
- Перекрывающиеся подзадачи: рекурсивное решение содержит небольшое количество отдельных подзадач, повторяющихся много раз.
Подобно техникам «Жадность» и «Разделяй и властвуй», DP не может решить все проблемы. Есть проблемы, которые нельзя решить никакими алгоритмическими методами [жадное, разделяй и властвуй и динамическое программирование].
Разница между динамическим программированием и простой рекурсией заключается в запоминании рекурсивных вызовов. Если подзадачи независимы и нет повторений, мемоизация не помогает, поэтому динамическое программирование не является решением всех проблем.
Подходы к динамическому программированию
В основном есть два подхода к решению проблем DP:
- Восходящее динамическое программирование (итеративное)
- Нисходящее динамическое программирование (рекурсивное)
Сверху вниз. Начните решать данную проблему с разбивки на части. Если вы видите, что проблема уже решена, просто верните сохраненный ответ. Если не решено, решите и сохраните ответ. Обычно это легко придумать и очень интуитивно понятно. Это называется мемоизацией.
Снизу вверх : проанализируйте проблему и посмотрите, в каком порядке решаются подзадачи, и начните решать от тривиальной подзадачи до данной проблемы. В этом процессе гарантируется, что подзадачи будут решены до решения проблемы. Это называется динамическим программированием.
Примеры алгоритмов динамического программирования
- Многие строковые алгоритмы, включая самую длинную общую подпоследовательность, самую длинную возрастающую подпоследовательность, самую длинную общую подстроку, расстояние редактирования.
- Алгоритмы на графах могут быть решены эффективно: алгоритм Беллмана-Форда для поиска кратчайшего расстояния в графе, алгоритм кратчайшего пути Флойда All-Pairs и т. Д.
- Цепное умножение матриц
- Сумма подмножества
- 0/1 Рюкзак
- Задача коммивояжера и многое другое
Создание рядов Фибоначчи с использованием динамического программирования
Если мы напишем ряд Фибоначчи с использованием nonDP, мы получим некоторую экспоненциальную сложность.
Подход «снизу вверх :
def Fibo(n): fibTable = [0, 1] for i in range(2,n+ 1 ): fibTable.append(fibTable[i-1] + fibTable[i-2]) return fibTable[n] print(Fibo(10})
Нисходящий подход :
fibTable = {1: 1, 2:1} def Fibo(n): if <= 2 : return 1 if n in fibTable: return fibTable[n] else: fibTable[n] = Fibo(n-1) + Fibo(n-2) return fibTable[n] print(Fibo(10))
Примечание. Обе версии реализаций ряда Фибоначчи явно снижают сложность задачи до O (n). Это потому, что если значение уже вычислено, мы больше не вызываем подзадачи. Вместо этого мы напрямую берем его значение из таблицы .
Сложность времени: O (n). Сложность пространства: O (n), для таблицы.
ПОСКОЛЬКУ НАМ НУЖНА СУММА ТОЛЬКО ПОСЛЕДНИХ ДВУХ ЗНАЧЕНИЙ, НАМ НЕ НУЖНО ХРАНИТЬ ВСЕ ЦЕННОСТИ PRIVIOS. МЫ МОЖЕМ УЛУЧШИТЬ ЭТО ТАК:
def Fibo(n): a, b = 0, 1 for i in range(n): a, b = b, a+ b return a print(Fibo(1O))
Сложность времени: O (n). Космическая сложность: O (1).
Точка, которую нужно держать в уме
Решая задачи с помощью DP, постарайтесь выяснить следующее:
- Посмотрите, как рекурсивно определяются проблемы в терминах подзадач.
- Посмотрим, можем ли мы использовать какую-нибудь таблицу [мемоизацию], чтобы избежать повторяющихся вычислений.
Куда пойти отсюда
Мой GitHub: https://github.com/myawesomehub
Мое сочинение: Ссылка
Продолжайте читать, чтобы получать больше полезных статей 👍
Спасибо!