游牧学院

7.5 强连通分量与Tarjan算法
8.2 最长公共子序列问题

动态规划的基本概念

动态规划（Dynamic Programming，简称DP）是一种用于解决最优化问题的算法设计方法。它通过将复杂问题分解为更简单的子问题，并存储这些子问题的结果，以避免重复计算，从而提高效率。动态规划广泛应用于计算机科学、运筹学、经济学等领域，尤其在算法竞赛和面试中经常出现。

1. 动态规划的基本思想

动态规划的基本思想是将一个复杂的问题分解为多个简单的子问题，并通过存储子问题的解来避免重复计算。动态规划通常适用于以下两种情况：

  1. 最优子结构：一个问题的最优解可以由其子问题的最优解构成。
  2. 重叠子问题：一个问题可以被分解为多个子问题，这些子问题在求解过程中会被多次计算。

1.1 最优子结构

最优子结构是指一个问题的最优解包含了其子问题的最优解。例如，在求解最短路径问题时，若从点A到点C的最短路径经过点B，则从A到B和B到C的路径也必须是最短的。

1.2 重叠子问题

重叠子问题是指在求解过程中，某些子问题会被多次计算。例如，在计算斐波那契数列时，F(n) = F(n-1) + F(n-2)，在计算F(n)时，F(n-1)和F(n-2)会被多次计算。

2. 动态规划的实现

动态规划的实现通常有两种方式：自顶向下（递归 + 记忆化）和自底向上（迭代）。下面将通过示例代码详细介绍这两种实现方式。

2.1 自顶向下（递归 + 记忆化）

在自顶向下的方法中，我们使用递归来解决问题，并通过一个数组来存储已经计算过的子问题的结果，以避免重复计算。

示例：斐波那契数列

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

# 测试
print(fib_memo(10))  # 输出 55

优点：

  • 代码简洁，易于理解。
  • 适合解决具有递归性质的问题。

缺点：

  • 递归深度可能导致栈溢出。
  • 可能会有较高的函数调用开销。

2.2 自底向上（迭代）

在自底向上的方法中，我们通过迭代的方式从最小的子问题开始，逐步构建到最终问题的解。

示例：斐波那契数列

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

# 测试
print(fib_bottom_up(10))  # 输出 55

优点：

  • 避免了递归带来的栈溢出问题。
  • 通常比递归方法更高效，因为没有函数调用的开销。

缺点：

  • 代码可能相对复杂，尤其在处理多维数组时。
  • 需要额外的空间来存储中间结果。

3. 动态规划的应用示例

动态规划可以应用于多种问题，以下是一些经典的动态规划问题及其解决方案。

3.1 0-1 背包问题

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

示例代码：

def knapsack(weights, values, capacity):
    n = len(values)
    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 = [1, 2, 3]
values = [60, 100, 120]
capacity = 5
print(knapsack(weights, values, capacity))  # 输出 220

优点：

  • 可以处理复杂的约束条件。
  • 适用于多种变体问题。

缺点：

  • 时间复杂度和空间复杂度较高，尤其在物品数量和容量较大时。

3.2 最长公共子序列

给定两个字符串，求它们的最长公共子序列的长度。

示例代码：

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]

# 测试
s1 = "ABCBDAB"
s2 = "BDCAB"
print(longest_common_subsequence(s1, s2))  # 输出 4

优点：

  • 可以有效地解决字符串匹配问题。
  • 适用于多种变体问题。

缺点：

  • 对于长字符串，时间和空间复杂度较高。

4. 注意事项

  1. 识别问题：在使用动态规划之前，首先要确认问题是否具有最优子结构和重叠子问题的性质。
  2. 状态定义：清晰地定义状态和状态转移方程是动态规划的关键。
  3. 空间优化：在某些情况下，可以通过滚动数组等技术来优化空间复杂度。
  4. 边界条件：注意处理边界条件，确保算法的正确性。

结论

动态规划是一种强大的算法设计技术，能够有效地解决许多复杂的最优化问题。通过合理的状态定义和状态转移方程，可以将问题的复杂度大大降低。尽管动态规划的实现可能会比较复杂，但掌握其基本思想和应用场景将为解决实际问题提供极大的帮助。

7.5 强连通分量与Tarjan算法
8.2 最长公共子序列问题