Динамическое программирование (DP) — популярный алгоритмический метод, используемый для решения задач оптимизации путем их разбиения на более мелкие подзадачи и повторного использования решений этих подзадач. Это широко используемый метод в кодировании интервью и соревнованиях по программированию. В этом сообщении блога мы обсудим, как определить и решить вопросы LeetCode, связанные с динамическим программированием, при программировании с использованием Python, с примером и подробным объяснением.

Выявление проблем динамического программирования
Есть несколько характеристик проблемы, которые указывают на то, что ее можно решить с помощью динамического программирования:

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

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

Чтобы проиллюстрировать этот процесс, мы будем использовать пример задачи из LeetCode.

Пример проблемы: сдача монет

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

Например, если у нас есть монеты номиналом [1, 5, 10] и нам нужно составить сумму 12, минимальное необходимое количество монет равно 2 (одна монета номиналом 10 и одна монета номиналом 2).

Шаг 1: определите оптимальную подструктуру
Чтобы решить эту проблему с помощью динамического программирования, нам нужно определить оптимальную подструктуру. Начнем с определения функции minCoins(n), которая возвращает минимальное количество монет, необходимое для получения суммы n.

Если у нас есть список номиналов монет [c1, c2, …, ck], мы можем рассмотреть два случая для каждого номинала монет:

Мы не используем номинал монеты ci. В этом случае минимальное количество монет, необходимое для составления суммы n, равно минимальному количеству монет, необходимому для составления суммы n, используя только номиналы монет [c1, c2, …, ci-1].

Мы используем номинал монеты ci. В этом случае минимальное количество монет, необходимое для составления суммы n, равно 1 + минимальное количество монет, необходимое для составления суммы n-ci с использованием номиналов монет [c1, c2, …, ci].

Оптимальную подструктуру задачи можно определить с помощью следующего рекуррентного соотношения:

minCoins(n) = min(minCoins(n-ci) + 1) для всех ci в номиналах монет

Шаг 2. Определите перекрывающиеся подпроблемы
Следующим шагом является выявление перекрывающихся подпроблем. Поскольку мы рекурсивно вычисляем минимальное количество монет, необходимое для каждой суммы, мы можем решить одну и ту же подзадачу несколько раз. Чтобы избежать избыточных вычислений, мы можем использовать мемоизацию для хранения решений подзадач.

Шаг 3. Разработка решения для динамического программирования
Чтобы разработать решение для динамического программирования, мы создадим массив мемоизации memo[n] для хранения минимального количества монет, необходимого для получения суммы n. . Мы инициализируем все значения в массиве бесконечными значениями, кроме memo[0], которому мы установим значение 0.

Затем мы воспользуемся восходящим подходом для заполнения массива мемоизации. Начиная с базового случая memo[0], мы будем перебирать все суммы от 1 до целевой суммы, заполняя минимальное количество монет, необходимое для каждой суммы. Для каждой суммы n мы перебираем все номиналы монет ci и вычисляем минимальное необходимое количество монет, используя рекуррентное соотношение:

memo[n] = min(memo[n-ci] + 1) для всех ci в номиналах монет

Как только мы заполнили массив мемоизации, решение задачи сохраняется в memo[target]. Если memo[target] по-прежнему равно бесконечности, то невозможно восполнить целевую сумму, используя заданные номиналы монет.

Вот код Python для динамического программирования решения проблемы размена монет:

def coinChange(coins, amount):
memo = [float('inf')] * (amount + 1)
memo[0] = 0

for n in range(1, amount+1):
    for c in coins:
        if c <= n:
            memo[n] = min(memo[n], memo[n-c] + 1)

return memo[amount] if memo[amount] != float('inf') else -1

Наилучший и наихудший случай пространственной и временной сложности
Временная сложность динамического программирования решения задачи размена монет составляет O(amount*k), где k — количество номиналов монет. Это связано с тем, что мы перебираем все суммы от 1 до целевой суммы, и для каждой суммы мы перебираем все номиналы монет. Поскольку размер массива мемоизации пропорционален целевому количеству, сложность пространства также равна O (количество).

В лучшем случае, если целевое количество равно 0, временная сложность равна O(k), потому что нам нужно только инициализировать массив мемоизации. В худшем случае, если невозможно восполнить целевую сумму, используя заданные номиналы монет, временная сложность составит O(сумма*k), потому что нам придется перебирать все суммы и номиналы монет, прежде чем определить, что решение верно. невозможно.

Заключение
Динамическое программирование — это мощный метод, который можно использовать для решения задач оптимизации, разбивая их на более мелкие подзадачи и повторно используя решения этих подзадач. При решении задач динамического программирования важно определить оптимальную подструктуру и перекрывающиеся подзадачи, а также разработать восходящее решение динамического программирования с использованием мемоизации. Следуя этим шагам и понимая наилучшие и наихудшие пространственные и временные сложности, мы можем эффективно решать вопросы LeetCode, связанные с динамическим программированием, при программировании на Python.