Опубликовано: 04.05.2025

Динамическое программирование — это широко распространённый алгоритмический метод, используемый для оптимизации рекурсивных решений, когда одни и те же подзадачи вызываются снова и снова множество раз, что замедляет получение результата.

• Основная идея динамического программирования заключается в хранении решений подзадач, чтобы каждая из них решалась только один раз.

• Чтобы решить задачу динамического программирования, мы сначала записываем рекурсивное решение таким образом, чтобы в дереве рекурсии были перекрывающиеся подзадачи (рекурсивная функция вызывается с одними и теми же параметрами несколько раз)

• Чтобы убедиться, что рекурсивное значение вычисляется только один раз (для сокращения времени выполнения алгоритма), мы сохраняем результаты рекурсивных вызовов.

Подходы динамического программирования (DP) на Python

Динамическое программирование на Python может быть достигнуто с помощью двух подходов:

• Сверху вниз – запоминание, мемоизация
• Снизу вверх – заполнение таблицы

1. Подход "сверху вниз" (запоминание):

При подходе «сверху вниз», также известном как запоминание, мы сохраняем рекурсивное решение и добавляем таблицу запоминания, чтобы избежать повторных вызовов одних и тех же подзадач.

• Прежде чем сделать какой-либо рекурсивный вызов, мы сначала проверяем, есть ли в таблице мемоизации решение для него.

• После завершения рекурсивного вызова мы сохраняем решение в таблице мемоизации.

2. Подход "снизу вверх" (сведение в таблицу):

При подходе «снизу вверх», также известном как табулирование, мы начинаем с самых маленьких подзадач и постепенно приходим к окончательному решению.

• Мы пишем итеративное решение (чтобы избежать накладных расходов на рекурсию) и строим решение снизу вверх.

• Мы используем таблицу динамического программирования, в которой сначала заполняем решение для базовых случаев, а затем заполняем остальные ячейки таблицы с помощью рекурсивной формулы.

• Мы используем рекурсивную формулу только для записей таблицы и не выполняем рекурсивных вызовов.

Подходы динамического программирования (DP)

Пример динамического программирования (DP)

Пример 1: рассмотрим задачу поиска последовательности Фибоначчи:

Последовательность Фибоначчи: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, …

Подход с применением грубой силы

Чтобы найти n-е число Фибоначчи методом перебора, нужно просто сложить (n-1)-е и (n-2)-е числа Фибоначчи.

def fib(n):
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)
print(fib(7))

Результат: 13

Как будет работать динамическое программирование (DP)?

Давайте теперь посмотрим на приведённое выше дерево рекурсии с перекрывающимися подзадачами, выделенными одним цветом. Мы ясно видим, что рекурсивное решение снова и снова выполняет большую работу, из-за чего временная сложность становится экспоненциальной. Представьте, сколько времени занимает вычисление большого числа Фибоначчи.

• Определите подзадачи: разделите основную задачу на более мелкие независимые подзадачи, то есть F(n-1) и F(n-2)

• Сохраните решения: решите каждую подзадачу и сохраните решение в таблице или массиве, чтобы нам не пришлось снова вычислять одно и то же.

• Постройте решения: Используйте сохранённые решения для построения решения основной задачи. Для F(n) найдите F(n-1) и F(n-2) в таблице и сложите их.

• Избегайте повторных вычислений: сохраняя решения, динамическое программирование гарантирует, что каждая подзадача (например, F(2)) решается только один раз, что сокращает время вычислений.

Использование подхода мемоизации — O(n) времени и O(n) памяти

Для этого в нашем примере мы просто используем массив-памятку, инициализированный значением -1. При рекурсивном вызове мы сначала проверяем, равно ли значение, сохранённое в массиве-памятке, соответствующему этой позиции, -1. Значение -1 указывает на то, что мы ещё не вычислили его и должны вычислить рекурсивно. Результат должен быть сохранён в массиве-памятке, чтобы в следующий раз, если встретится, то же значение, его можно было напрямую использовать из массива-памятки.

def fibRec(n, memo):
    if n <= 1:
        return n
    # Проверка на существование данного вычисления
    if memo[n] != -1:
        return memo[n]
    # Вычисление и сохранение для дальнейшего использования
    memo[n] = fibRec(n - 1, memo) + \
              fibRec(n - 2, memo)
    return memo[n]
def fib(n):
    memo = [-1] * (n + 1)
    return fibRec(n, memo)
print(fib(7))

Результат: 13

Использование табличного подхода — O(n) времени и O(n) памяти

В этом подходе мы используем массив размером (n + 1), часто называемый dp[], для хранения чисел Фибоначчи. Массив инициализируется базовыми значениями по соответствующим индексам, например dp[0] = 0 и dp[1] = 1. Затем мы итеративно вычисляем значения Фибоначчи от dp[2] до dp[n], используя соотношение dp[i] = dp[i-1] + dp[i-2]. Это позволяет нам эффективно вычислять числа Фибоначчи в цикле. Наконец, значение в dp[n] даёт число Фибоначчи для входного значения n, поскольку каждый индекс содержит ответ для соответствующего числа Фибоначчи.

def fibo(n):
    dp = [0] * (n + 1)
    # Хранение независимых значений в динамическом программировании
    dp[0] = 0
    dp[1] = 1
    # Использование подхода "снизу вверх"
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]
print(fibo(7))

Результат: 13

Использование оптимизированного по пространству подхода — O(n) времени и O(1) пространства

В приведенном выше коде мы видим, что текущее состояние любого числа Фибоначчи зависит только от двух предыдущих значений. Поэтому нам не нужно хранить всю таблицу размером n+1, вместо этого мы можем хранить только два предыдущих значения.

def fibo(n):
    prevPrev, prev, curr = 0, 1, 1
    # Using the bottom-up approach
    for i in range(2, n + 1):
        curr = prev + prevPrev
        prevPrev = prev
        prev = curr
    return curr
print(fibo(7))

Результат: 13

Часто задаваемые вопросы

1. Что такое динамическое программирование?

Динамическое программирование (ДП) — это метод, используемый для решения задач путём разбиения их на более мелкие подзадачи. Он позволяет сохранять результаты решения подзадач, чтобы избежать лишних вычислений и повысить эффективность алгоритма.

2. Чем динамическое программирование отличается от "Разделяй и властвуй"?

Метод «разделяй и властвуй»: разбивает задачу на непересекающиеся подзадачи и решает их по отдельности.

Динамическое программирование: решает перекрывающиеся подзадачи путём сохранения решений ранее вычисленных подзадач.

3. Когда я должен использовать динамическое программирование?

Используйте динамическое программирование, когда задачу можно разбить на перекрывающиеся подзадачи, а также когда есть оптимальная структура и перекрывающиеся подзадачи. К распространённым примерам относятся такие задачи, как вычисление ряда Фибоначчи, поиск кратчайшего пути и задача о рюкзаке.

4. Можно ли использовать динамическое программирование для всех задач?

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

Оригинал статьи

Рубрики по темам:

• Родительские собрания
• Статьи об IT
• Справочник IT
• Python вопрос/ответ
• Статьи о Дизайне