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

Метод 1: последовательность Фибоначчи
Последовательность Фибоначчи — это классический пример, используемый для объяснения динамического программирования. Задача состоит в том, чтобы найти n-е число Фибоначчи, где каждое число в последовательности представляет собой сумму двух предыдущих. В этом случае для оптимизации рекурсивного подхода можно использовать динамическое программирование.

def fibonacci(n):
    fib = [0, 1]
    for i in range(2, n+1):
        fib.append(fib[i-1] + fib[i-2])
    return fib[n]

Метод 2: Задача о размене монет
Задача о размене монет включает в себя нахождение минимального количества монет, необходимого для получения заданной суммы денег. Учитывая список номиналов монет, для эффективного решения этой проблемы можно использовать динамическое программирование.

def coin_change(coins, amount):
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0
    for coin in coins:
        for i in range(coin, amount + 1):
            dp[i] = min(dp[i], dp[i - coin] + 1)
    return dp[amount] if dp[amount] != float('inf') else -1

Метод 3: самая длинная общая подпоследовательность
Задача о самой длинной общей подпоследовательности (LCS) включает в себя поиск самой длинной подпоследовательности, которая присутствует в двух заданных последовательностях. Для эффективного решения этой проблемы можно использовать динамическое программирование.

def longest_common_subsequence(s1, s2):
    m, n = len(s1), len(s2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i - 1] == s2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    return dp[m][n]

Метод 4: Задача о рюкзаке
Задача о рюкзаке включает в себя выбор подмножества предметов с максимальной ценностью с учетом ограничения по весу. Для решения этой проблемы оптимизации можно использовать динамическое программирование.

def knapsack(weights, values, capacity):
    n = len(weights)
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for j in range(1, capacity + 1):
            if weights[i - 1] <= j:
                dp[i][j] = max(values[i - 1] + dp[i - 1][j - weights[i - 1]], dp[i - 1][j])
            else:
                dp[i][j] = dp[i - 1][j]
    return dp[n][capacity]

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