Динамическое программирование

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

Представьте, что вы поднимаетесь поnлестнице с n ступенями. Каждый раз вы можете подняться на1ступеньку или2ступеньки.

Итак, сколько существует различных способов подняться на вершину здания?

Если вы начнёте с самой верхней цели (сnn-й ступени), это может показаться сложным.

Но если мы изменим точку зрения:Чтобы достичьnn. Чтобы достичь ступени n, можно толькоn-1подняться на одну ступеньку вверх от ступени n-1 или сn-2уровня, поднявшись на две ступеньки.. Итак, чтобы достичьnЧисло способов достичь ступени n равно числу способов достичь ступениn-1n-1 плюс число способов достичь ступениn-2уровня, число способов.

Такого родаразбиение большой задачи на несколько перекрывающихся подзадач и избегание повторных вычислений путём сохранения решений подзадач, тем самым эффективное решение исходной задачи.Этот метод — динамическое программирование (сокращённо DP).

Основная идея

Суть динамического программирования —запоминать уже вычисленные решения. 。

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

  1. перекрывающиеся подзадачи: в процессе рекурсивного решения одна и та же подзадача может вычисляться несколько раз.
  2. Оптимальная подструктура: оптимальное решение задачи содержит оптимальные решения её подзадач.

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

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


От рекурсии к динамическому программированию: задача о подъёме по лестнице

давайте воспользуемся задачейClimbing Stairs, чтобы пройти процесс оптимизации от рекурсии к динамическому программированию.

Описание проблемы

Предположим, вы поднимаетесь по лестнице. Вам нужноnступеней, прежде чем сможете достичь вершины. Каждый раз вы можете подняться на1или2ступеньки. Сколько существует различных способов подняться на вершину?

Метод 1: наивная рекурсия (неэффективно)

Основываясь на анализе в начале, мы можем сразу написать рекурсивный код.f(n) = f(n-1) + f(n-2)где,f(1) = 1, f(2) = 2。

Пример

def climb_stairs_recursive(n: int) -> int:
    """Рекурсивное решение"""
    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") для хранения уже вычисленных результатов и избежать повторных вычислений.

Пример

def climb_stairs_memo(n: int) -> int:
    """Рекурсия с мемоизацией (сверху вниз)"""
    # Инициализируем таблицу мемоизации; -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для хранения состояний.

Пример

def climb_stairs_dp(n: int) -> int:
    """Динамическое программирование (снизу вверх)"""
    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массив; просто используйте две переменные для обновления скользящим способом.

Пример

def climb_stairs_optimized(n: int) -> int:
    """Динамическое программирование (версия с оптимизацией памяти)"""
    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)

Пример

def fibonacci(n: int) -> int:
    """Вычисляет числа Фибоначчи с помощью динамического программирования"""
    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

  1. Определите состояние:dp[i]представляет составление общей суммыiминимальное количество монет, необходимое.
  2. уравнение перехода состояний: Для суммыi, мы можем перебрать каждый номинал монетыcoin. Еслиcoin <= i, затем набрать суммуiОдин из возможных способов: сначала набрать суммуi - coin, затем добавить одну монетуcoinноминал монеты. Нам нужно найти минимум среди всех возможностей. Поэтому уравнение можно записать так:dp[i] = min(dp[i], dp[i - coin] + 1), для всех, которые удовлетворяютcoin <= iизcoin。
  3. Начальные условия:dp[0] = 0, для набора суммы 0 требуется 0 монет. Остальныеdp[i]инициализируются очень большим числом (например,amount + 1илиfloat('inf')), что означает, что пока её нельзя набрать.
  4. Порядок вычислений: снизу вверх, отi=1Вычисляем доi=amount。

Реализация кода

Пример

def coin_change(coins: list, amount: int) -> int:
    """Размен монет — динамическое программирование"""
    # Инициализируем массив 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 (содержащий только себя).
Другие расширения