常用动态规划算法

常用动态规划算法:

动态规划原理

动态规划（Dynamic Programming, DP）是一种将复杂问题分解为更小子问题的方法。通过记录中间结果（即子问题的解），避免重复计算，最终解决原问题。核心思想包括：

1. 分解问题：将原问题分解为互相独立的子问题。

2. 记录结果：使用表格或其他数据结构保存中间子问题的解。

3. 构造解法：通过中间结果逐步解决更大的子问题，直至解决原问题。

核心步骤

• 状态定义：确定问题的状态（通常是子问题的解法所依赖的变量）。

• 状态转移方程：明确如何通过较小的状态计算较大的状态。

• 初始状态和边界条件：定义起点和特例处理。

• 结果提取：从表格或数据结构中获取最终答案。

动态规划经典算法及Python示例

1. 斐波那契数列

原理：每个数字等于前两个数字之和。

状态定义：dp[i] 表示第 i 个斐波那契数。

状态转移方程：dp[i] = dp[i-1] + dp[i-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. 最短路径（如三角形路径和问题）

问题描述：给定一个三角形，从顶部到底部选择一条路径，使路径和最小。

状态定义：dp[i][j] 表示到达位置 (i, j) 的最小路径和。

状态转移方程：dp[i][j] = min(dp[i-1][j], dp[i-1][j-1]) + triangle[i][j]。

def minimum_path_sum(triangle):
    n = len(triangle)
    dp = triangle[-1]
    for i in range(n - 2, -1, -1):
        for j in range(i + 1):
            dp[j] = triangle[i][j] + min(dp[j], dp[j + 1])
    return dp[0]
​
triangle = [
    [2],
    [3, 4],
    [6, 5, 7],
    [4, 1, 8, 3]
]
print(minimum_path_sum(triangle))  # 输出：11

用途：路径规划、游戏地图分析。

3. 最长公共子序列（LCS）

问题描述：给定两个字符串，找出它们的最长公共子序列。

状态定义：dp[i][j] 表示字符串 text1[0:i] 和 text2[0:j] 的最长公共子序列长度。

状态转移方程：

• 若 text1[i-1] == text2[j-1]：dp[i][j] = dp[i-1][j-1] + 1

• 否则：dp[i][j] = max(dp[i-1][j], dp[i][j-1])

def longest_common_subsequence(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]
​
print(longest_common_subsequence("abcde", "ace"))  # 输出：3

用途：DNA序列比对、文本比较。

4. 背包问题（0-1背包）

问题描述：在容量限制下，从一组物品中选择子集，使总价值最大。

状态定义：dp[i][w] 表示前 i 件物品中最大重量为 w 时的最大价值。

状态转移方程：

• 若不选第 i 件：dp[i][w] = dp[i-1][w]

• 若选第 i 件：dp[i][w] = max(dp[i-1][w], dp[i-1][w-weight[i]] + value[i])

def knapsack(weights, values, capacity):
    n = len(weights)
    dp = [0] * (capacity + 1)
    for i in range(n):
        for w in range(capacity, weights[i] - 1, -1):
            dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
    return dp[capacity]
​
weights = [1, 3, 4, 5]
values = [1, 4, 5, 7]
capacity = 7
print(knapsack(weights, values, capacity))  # 输出：9

用途：资源分配、投资决策。

5. 编辑距离

问题描述：计算将字符串 word1 转换为 word2 所需的最少编辑操作（插入、删除、替换）。

状态定义：dp[i][j] 表示将 word1[0:i] 转换为 word2[0:j] 的最少操作数。

状态转移方程：

• 若 word1[i-1] == word2[j-1]：dp[i][j] = dp[i-1][j-1]

• 否则：dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])

def min_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]
​
print(min_distance("horse", "ros"))  # 输出：3

用途：拼写纠错、自然语言处理。

动态规划的用途

1. 优化递归：解决子问题重复计算的问题。

2. 路径规划：如最短路径、最小成本路径。

3. 文本处理：如字符串匹配、文本相似度计算。

4. 资源分配：如背包问题、投资分配。

5. 生物信息学：如基因序列对比、蛋白质结构比对。

6. 游戏AI：如棋盘路径规划