Разъяснение с примерами. Просто взгляните и дайте мне знать, что думаете по этому поводу!

Обзор

Динамическое программирование и мемоизация работают вместе. Основное различие между динамическим программированием и разделяй и властвуй состоит в том, что в последнем случае подзадачи независимы, тогда как в 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

Мое сочинение: Ссылка

Продолжайте читать, чтобы получать больше полезных статей 👍
Спасибо!