跳到主要内容

动态规划基础

动态规划（Dynamic Programming，简称 DP）是一种用于解决复杂问题的算法设计技术。它通过将问题分解为更小的子问题，并存储子问题的解以避免重复计算，从而高效地解决问题。动态规划通常用于优化问题，例如最短路径、最长公共子序列、背包问题等。

动态规划的核心思想​

动态规划的核心思想可以概括为以下三点：

  1. 分治：将原问题分解为若干子问题。
  2. 存储：存储子问题的解，避免重复计算。
  3. 递推：通过子问题的解推导出原问题的解。

动态规划通常适用于具有重叠子问题和最优子结构性质的问题。

备注

重叠子问题：子问题在求解过程中会被多次重复计算。
最优子结构：问题的最优解可以通过子问题的最优解推导出来。

动态规划的两种实现方式​

动态规划的实现方式通常有两种：

  1. 自顶向下（Top-Down）：也称为记忆化搜索。从原问题开始，递归地分解为子问题，并存储子问题的解。
  2. 自底向上（Bottom-Up）：从最小的子问题开始，逐步递推，直到解决原问题。

自顶向下示例：斐波那契数列​

斐波那契数列是一个经典的动态规划问题。其定义如下：

  • F(0) = 0
  • F(1) = 1
  • F(n) = F(n-1) + F(n-2)（当 n >= 2 时）

以下是使用自顶向下方法的代码实现：

python
def fibonacci(n, memo={}):
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    memo[n] = fibonacci(n-1, memo) + fibonacci(n-2, memo)
    return memo[n]

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

自底向上示例：斐波那契数列​

自底向上的方法通过递推的方式计算斐波那契数列：

python
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
提示

自底向上的方法通常更高效，因为它避免了递归调用的开销。

动态规划的典型问题​

1. 背包问题​

背包问题是动态规划的经典应用之一。问题描述如下：

  • 给定一组物品，每个物品有重量和价值。
  • 背包有一个最大承重限制。
  • 目标是在不超过承重限制的情况下，选择物品使得总价值最大。

代码实现​

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(knapsack(weights, values, capacity))  # 输出：7

2. 最长公共子序列（LCS）​

最长公共子序列问题是另一个经典的动态规划问题。给定两个字符串，找到它们的最长公共子序列。

代码实现​

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(lcs(text1, text2))  # 输出：3

动态规划的实际应用​

动态规划在现实生活中有广泛的应用，例如：

  1. 路径规划：在地图应用中寻找最短路径。
  2. 资源分配：在项目管理中优化资源分配。
  3. 生物信息学：用于 DNA 序列比对。

总结​

动态规划是一种强大的算法设计技术，适用于具有重叠子问题和最优子结构性质的问题。通过分治、存储和递推，动态规划能够高效地解决复杂问题。掌握动态规划的关键在于理解问题的结构，并选择合适的实现方式（自顶向下或自底向上）。

附加资源与练习​

  1. 练习：尝试解决以下问题：
  2. 推荐阅读：
警告

动态规划的学习需要大量练习，建议从简单问题开始，逐步深入。