动态规划实例

动态规划是一种算法设计技巧，它将复杂问题分解为更小的子问题，并存储子问题的解以避免重复计算。以下是一些动态规划的实例：

1. 斐波那契数列

斐波那契数列是动态规划的一个经典实例。数列定义为：F(0) = 0, F(1) = 1, F(n) = F(n-1) + F(n-2)。

def fibonacci(n):
    if n <= 1:
        return n
    dp = [0] * (n + 1)
    dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]

print(fibonacci(10))  # 输出：55

2. 最长公共子序列

最长公共子序列问题是找出两个序列中最长的相同子序列。

def longest_common_subsequence(X, Y):
    m, n = len(X), len(Y)
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if X[i - 1] == Y[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]

print(longest_common_subsequence("ABCBDAB", "BDCAB"))  # 输出：4

3. 背包问题

背包问题是动态规划中另一个常见的实例，它涉及到在一个给定的背包容量下，如何选择物品以最大化价值。

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 w in range(1, capacity + 1):
            if weights[i - 1] <= w:
                dp[i][w] = max(values[i - 1] + dp[i - 1][w - weights[i - 1]], dp[i - 1][w])
            else:
                dp[i][w] = dp[i - 1][w]

    return dp[n][capacity]

print(knapsack([1, 3, 4, 5], [1, 4, 5, 7], 8))  # 输出：12

更多动态规划算法和实例，请参考本站的动态规划教程。