Динамическое программирование
Динамическое программирование (англ.: Dynamic programming, сокращённо DP) — метод, используемый в математике, науке управления, информатике, экономике и биоинформатике, который решает сложные задачи путём разбиения исходной задачи на относительно простые подзадачи.
Представьте, что вы поднимаетесь по
nлестнице с n ступенями. Каждый раз вы можете подняться на1ступеньку или2ступеньки.Итак, сколько существует различных способов подняться на вершину здания?
Если вы начнёте с самой верхней цели (с
nn-й ступени), это может показаться сложным.Но если мы изменим точку зрения:Чтобы достичь
nn. Чтобы достичь ступени n, можно толькоn-1подняться на одну ступеньку вверх от ступени n-1 или сn-2уровня, поднявшись на две ступеньки.. Итак, чтобы достичьnЧисло способов достичь ступени n равно числу способов достичь ступениn-1n-1 плюс число способов достичь ступениn-2уровня, число способов.
Такого родаразбиение большой задачи на несколько перекрывающихся подзадач и избегание повторных вычислений путём сохранения решений подзадач, тем самым эффективное решение исходной задачи.Этот метод — динамическое программирование (сокращённо DP).
Основная идея
Суть динамического программирования —запоминать уже вычисленные решения. 。
Динамическое программирование обычно используется для решения задач со следующими свойствами:
- перекрывающиеся подзадачи: в процессе рекурсивного решения одна и та же подзадача может вычисляться несколько раз.
- Оптимальная подструктура: оптимальное решение задачи содержит оптимальные решения её подзадач.
Мы можем использовать простую блок-схему, чтобы понять подход динамического программирования к решению задач:
На рисунке выше показаны типичные шаги решения задачи динамического программирования: начните с определения задачи, найдите структуру подзадач путём анализа, затем формализуйте её с помощью состояний и уравнений переходов между состояниями и, наконец, получите ответ с помощью ясных начальных условий и порядка вычислений.
От рекурсии к динамическому программированию: задача о подъёме по лестнице
давайте воспользуемся задачейClimbing Stairs, чтобы пройти процесс оптимизации от рекурсии к динамическому программированию.
Описание проблемы
Предположим, вы поднимаетесь по лестнице. Вам нужноnступеней, прежде чем сможете достичь вершины. Каждый раз вы можете подняться на1или2ступеньки. Сколько существует различных способов подняться на вершину?
Метод 1: наивная рекурсия (неэффективно)
Основываясь на анализе в начале, мы можем сразу написать рекурсивный код.f(n) = f(n-1) + f(n-2)где,f(1) = 1, f(2) = 2。
Пример
"""Рекурсивное решение"""
if n == 1:
return 1
if n == 2:
return 2
return climb_stairs_recursive(n - 1) + climb_stairs_recursive(n - 2)
#
print(f"Количество способов подняться на 5-ю ступеньку (рекурсия): {climb_stairs_recursive(5)}") # Вывод: 8
Disadvantages Analysis: эта рекурсия включает большое количество повторных вычислений. Например, вычислениеf(5)требуетf(4)иf(3), вычисляяf(4)в свою очередь требуетf(3)иf(2), здесьf(3)вычисляется дважды. Когдаnn велико, временная сложность экспоненциальна.O(2^n), что крайне неэффективно.
Метод 2: Рекурсия с мемоизацией (сверху вниз)
Мы можем использовать массив ("memo") для хранения уже вычисленных результатов и избежать повторных вычислений.
Пример
"""Рекурсия с мемоизацией (сверху вниз)"""
# Инициализируем таблицу мемоизации; -1 означает, что значение не вычислено
memo = [-1] * (n + 1)
def helper(x: int) -> int:
# Базовый случай
if x == 1:
return 1
if x == 2:
return 2
# Если уже вычислено, вернуть результат напрямую
if memo[x] != -1:
return memo[x]
# Иначе вычислить и сохранить в таблице мемоизации
memo[x] = helper(x - 1) + helper(x - 2)
return memo[x]
return helper(n)
print(f"Количество способов подняться на 5-ю ступеньку (мемоизация): {climb_stairs_memo(5)}") # Вывод: 8
Временная сложность этого метода снижена доO(n), потому что каждая подзадача вычисляется только один раз. Пространственная сложность равнаO(n). Это уже подход динамического программирования, называемый«нисходящий»или«поиск с мемоизацией»。
Метод 3: Итеративный массив (снизу вверх, стандартное ДП)
Мы начинаем непосредственно с наименьшей подзадачи и шаг за шагом доходим до исходной задачи. Обычно используется массивdpдля хранения состояний.
Пример
"""Динамическое программирование (снизу вверх)"""
if n <= 2:
return n
# 1. Определите массив состояний: dp[i] представляет количество способов подняться на i-ю ступеньку
dp = [0] * (n + 1)
# 2. Определите начальные условия
dp[1] = 1
dp[2] = 2
# 3. Переход состояний: выведите рекурсивно согласно уравнению перехода состояний
for i in range(3, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]
# 4. Верните итоговый результат
return dp[n]
print(f"Количество способов подняться на 5-ю ступеньку (DP): {climb_stairs_dp(5)}") # Вывод: 8
Метод 4: оптимизация пространства (скользящий массив)
Обратите внимание на уравнение перехода состоянийdp[i] = dp[i-1] + dp[i-2], мы обнаруживаем, что текущее состояние зависит только от двух предыдущих состояний. Поэтому нам не нужно хранить весьdpмассив; просто используйте две переменные для обновления скользящим способом.
Пример
"""Динамическое программирование (версия с оптимизацией памяти)"""
if n <= 2:
return n
# Использовать только две переменные для представления dp[i-1] и dp[i-2]
prev, curr = 1, 2 # Соответствуют dp[1], dp[2]
for i in range(3, n + 1):
# Вычислить новое текущее значение
new_curr = prev + curr
# Скользящее обновление переменных, подготовка к следующей итерации цикла
prev, curr = curr, new_curr
return curr
print(f"Количество способов подняться на 5-ю ступеньку (оптимизированное ДП): {climb_stairs_optimized(5)}") # Вывод: 8
После оптимизации пространственная сложность уменьшается сO(n)снизилась доO(1)。
Схема решения задач динамического программирования
На примере задачи о подъёме по лестнице можно обобщить универсальный четырёхшаговый процесс решения задач динамического программирования:
Шаг 1: Определите состояние
Используйте один или несколько массивов (обычно называемыхdp) для представления решений подзадач. Ключ в том, чтобы чётко понятьdp[i]илиdp[i][j]Что он обозначает?
В задаче о подъёме по лестнице мы определяем
dp[i]как «подъём доiобщее количество способов достичь ступени n.
Шаг 2: Определите уравнение перехода состояний
найтиdp[i]с предыдущим состоянием (таким какdp[i-1], dp[i-2]связь между ними. В этом суть и сложность динамического программирования.
В задаче о подъёме по лестнице уравнение перехода состояний имеет вид:
dp[i] = dp[i-1] + dp[i-2]。
Шаг 3: Определите начальные условия (базовый случай).
Решения наименьших неделимых подзадач. Это начальная точка рекуррентного соотношения, и её нужно задать вручную.
В задаче о подъёме по лестнице начальные условия таковы:
dp[1] = 1,dp[2] = 2。
Шаг 4: Определите порядок вычислений и вычислите
Определите, является ли он "нисходящим" (рекурсия с мемоизацией) или "восходящим" (итеративная рекуррентность), и убедитесь, что при вычисленииdp[i], все подзадачи, от которых он зависит, уже вычислены.
В задаче о подъёме по лестнице мы применяем восходящий подход, начиная с
i=3цикл доi=n。
Классический пример: последовательность Фибоначчи
Последовательность Фибоначчи — наиболее наглядный пример динамического программирования; само её определение и есть уравнение перехода состояний.
Задача: найти n-е число Фибоначчиnчлен.F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2) (n>=2)
Пример
"""Вычисляет числа Фибоначчи с помощью динамического программирования"""
if n < 2:
return n
# Реализация с оптимизацией по памяти
prev, curr = 0, 1 # F(0), F(1)
for _ in range(2, n + 1):
prev, curr = curr, prev + curr
return curr
# Тестовые данные
test_n = 10
print(f"{test_n}-й член последовательности Фибоначчи равен: {fibonacci(test_n)}") # Вывод: 55
Продвинутый пример: размен монет
Это более типичная задача, демонстрирующая оптимальную подструктуру.
Описание задачи: дан целочисленный массивcoins, представляющий монеты различных номиналов, и целое числоamount, представляющий общую сумму. Вычислите и верните минимальное количество монет, необходимое для составления общей суммы. Если ни одна комбинация монет не может составить общую сумму, верните-1. Можно предположить, что количество каждой монеты неограниченно.
Анализ задачи и проектирование DP
- Определите состояние:
dp[i]представляет составление общей суммыiминимальное количество монет, необходимое. - уравнение перехода состояний: Для суммы
i, мы можем перебрать каждый номинал монетыcoin. Еслиcoin <= i, затем набрать суммуiОдин из возможных способов: сначала набрать суммуi - coin, затем добавить одну монетуcoinноминал монеты. Нам нужно найти минимум среди всех возможностей. Поэтому уравнение можно записать так:dp[i] = min(dp[i], dp[i - coin] + 1), для всех, которые удовлетворяютcoin <= iизcoin。 - Начальные условия:
dp[0] = 0, для набора суммы 0 требуется 0 монет. Остальныеdp[i]инициализируются очень большим числом (например,amount + 1илиfloat('inf')), что означает, что пока её нельзя набрать. - Порядок вычислений: снизу вверх, от
i=1Вычисляем доi=amount。
Реализация кода
Пример
"""Размен монет — динамическое программирование"""
# Инициализируем массив dp, где dp[i] обозначает минимальное количество монет для суммы i
# Задаём недостижимое начальное значение amount + 1
dp = [amount + 1] * (amount + 1)
dp[0] = 0 # Когда сумма равна 0, нужно 0 монет
# Внешний цикл: перебираем все состояния суммы
for i in range(1, amount + 1):
# Внутренний цикл: перебираем все варианты монет
for coin in coins:
# Если номинал текущей монеты меньше или равен текущей сумме, рассматриваем использование этой монеты
if coin <= i:
# Переход состояния: dp[i] — это решение без использования текущей монеты и
# меньшее значение среди решений, использующих текущую монету (т. е. dp[i-coin] + 1)
dp[i] = min(dp[i], dp[i - coin] + 1)
# Если dp[amount] не был обновлён (всё ещё исходное значение), это означает, что сумму невозможно составить
return dp[amount] if dp[amount] <= amount else -1
# Тестовые данные
coins = [1, 2, 5]
amount = 11
print(f"Минимальное количество монет, необходимое для составления общей суммы {amount}, равно: {coin_change(coins, amount)}") # Вывод: 3 (5+5+1)
Практические упражнения
Пожалуйста, попробуйте решить следующие задачи самостоятельно, чтобы закрепить своё понимание динамического программирования:
Упражнение 1: Максимальная сумма подмассива
Задан целочисленный массивnums, найдите непрерывный подмассив с максимальной суммой и верните его максимальную сумму.
Пример:
输入:nums = [-2,1,-3,4,-1,2,1,-5,4] 输出:6 解释:连续子数组 [4,-1,2,1] 的和最大,为 6。
Подсказка:
- определение
dp[i]как "сiмаксимальная сумма непрерывного подмассива, заканчивающегося элементом". - уравнение перехода состояний:
dp[i] = max(nums[i], dp[i-1] + nums[i])。 - Итоговый ответ — это все
dp[i]максимум среди них.
Упражнение 2: самая длинная возрастающая подпоследовательность
Задан целочисленный массивnums, найдите длину самой длинной строго возрастающей подпоследовательности.
Пример:
输入:nums = [10,9,2,5,3,7,101,18] 输出:4 解释:最长递增子序列是 [2,3,7,101],因此长度为 4。
Подсказка:
- определение
dp[i]как "сiдлина самой длинной возрастающей подпоследовательности, заканчивающейся числом". - Для каждого
i, нужно перебратьjfrom0вi-1, еслиnums[i] > nums[j], затемdp[i] = max(dp[i], dp[j] + 1)。 - Изначально каждый
dp[i]по крайней мере 1 (содержащий только себя).
