python 动态规划

动态规划

动态规划（Dynamic Programming, DP）是一种用于解决具有重叠子问题和最优子结构问题的算法设计方法。它通过将问题分解为子问题，并存储子问题的解，避免重复计算，从而提高效率。

以下是常见的动态规划问题及其 Python 实现：

1. 斐波那契数列

斐波那契数列是动态规划的经典问题，定义为：
F(0) = 0, F(1) = 1, F(n) = F(n-1) + F(n-2)

时间复杂度：

• 递归：O(2^n)
• 动态规划：O(n)

Python 实现

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

# 示例使用
n = 10
print(f"斐波那契数列第 {n} 项: {fibonacci(n)}")

2. 背包问题（Knapsack Problem）

背包问题是一个经典的组合优化问题。给定一组物品，每个物品有重量和价值，在不超过背包容量的情况下，选择物品使得总价值最大。

时间复杂度：

• O(n * W)，其中 n 是物品数量，W 是背包容量。

Python 实现

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

# 示例使用
weights = [2, 3, 4, 5]
values = [3, 4, 5, 6]
capacity = 5
print(f"背包问题的最大价值: {knapsack(weights, values, capacity)}")

3. 最长公共子序列（LCS, Longest Common Subsequence）

最长公共子序列问题用于找到两个序列的最长公共子序列的长度。

时间复杂度：

• O(m * n)，其中 m 和 n 分别是两个序列的长度。

Python 实现

def lcs(text1, text2):
    m, n = len(text1), len(text2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if text1[i - 1] == text2[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]

# 示例使用
text1 = "abcde"
text2 = "ace"
print(f"最长公共子序列的长度: {lcs(text1, text2)}")

4. 最长递增子序列（LIS, Longest Increasing Subsequence）

最长递增子序列问题用于找到一个序列中最长的严格递增子序列的长度。

时间复杂度：

• O(n²)，其中 n 是序列的长度。

Python 实现

def lis(nums):
    n = len(nums)
    dp = [1] * n
    
    for i in range(1, n):
        for j in range(i):
            if nums[i] > nums[j]:
                dp[i] = max(dp[i], dp[j] + 1)
    
    return max(dp)

# 示例使用
nums = [10, 9, 2, 5, 3, 7, 101, 18]
print(f"最长递增子序列的长度: {lis(nums)}")

5. 矩阵链乘法（Matrix Chain Multiplication）

矩阵链乘法问题用于找到矩阵相乘的最优顺序，使得计算的总代价最小。

时间复杂度：

• O(n³)，其中 n 是矩阵的数量。

Python 实现

def matrix_chain_order(dims):
    n = len(dims) - 1
    dp = [[0] * n for _ in range(n)]
    
    for length in range(2, n + 1):  # 子问题的长度
        for i in range(n - length + 1):
            j = i + length - 1
            dp[i][j] = float('inf')
            for k in range(i, j):
                cost = dp[i][k] + dp[k + 1][j] + dims[i] * dims[k + 1] * dims[j + 1]
                if cost < dp[i][j]:
                    dp[i][j] = cost
    
    return dp[0][n - 1]

# 示例使用
dims = [30, 35, 15, 5, 10, 20, 25]
print(f"矩阵链乘法的最小计算代价: {matrix_chain_order(dims)}")

6. 编辑距离（Edit Distance）

编辑距离问题用于计算将一个字符串转换为另一个字符串所需的最少操作次数（插入、删除、替换）。

时间复杂度：

• O(m * n)，其中 m 和 n 分别是两个字符串的长度。

Python 实现

def edit_distance(word1, word2):
    m, n = len(word1), len(word2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    for i in range(m + 1):
        for j in range(n + 1):
            if i == 0:
                dp[i][j] = j
            elif j == 0:
                dp[i][j] = i
            elif word1[i - 1] == word2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]
            else:
                dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1])
    
    return dp[m][n]

# 示例使用
word1 = "horse"
word2 = "ros"
print(f"编辑距离: {edit_distance(word1, word2)}")

总结

动态规划通过将问题分解为子问题并存储子问题的解，能够高效地解决许多复杂问题。