算法设计技巧 5.3 动态规划的原理与典型问题

动态规划（Dynamic Programming，DP）是一种解决复杂问题的方法，特别适用于具有重叠子问题和最优子结构性质的问题。动态规划通过将问题分解为更小的子问题，存储这些子问题的结果，从而避免重复计算，显著提高算法的效率。

1. 动态规划的基本原理

动态规划的核心思想是将一个复杂问题分解为多个简单的子问题，并通过存储子问题的解来避免重复计算。动态规划通常有两种实现方式：自顶向下（递归 + 记忆化）和自底向上（迭代）。

1.1 最优子结构

一个问题具有最优子结构性质，意味着其最优解可以由其子问题的最优解构成。换句话说，若一个问题的最优解包含了其子问题的最优解，则该问题具有最优子结构。

1.2 重叠子问题

重叠子问题是指在解决问题的过程中，出现了相同的子问题多次。动态规划通过存储这些子问题的解来避免重复计算，从而提高效率。

2. 动态规划的实现方式

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

在自顶向下的方法中，我们通常使用递归来解决问题，并使用一个数据结构（如数组或哈希表）来存储已经计算过的子问题的结果。

示例：斐波那契数列

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

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

2.2 自底向上（迭代）

在自底向上的方法中，我们从最小的子问题开始，逐步构建到原问题的解。通常使用一个数组来存储子问题的解。

示例：斐波那契数列

def fib(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(fib(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. 动态规划的优缺点

4.1 优点

高效性：通过存储子问题的解，避免了重复计算，显著提高了算法的效率。
适用性广：动态规划可以解决许多复杂问题，如背包问题、最短路径问题、字符串匹配等。
结构清晰：动态规划的思路通常较为清晰，易于理解和实现。

4.2 缺点

空间复杂度：动态规划通常需要额外的空间来存储子问题的解，可能导致空间复杂度较高。
实现复杂性：对于某些问题，动态规划的实现可能较为复杂，需要仔细分析问题的结构。
不适用所有问题：并非所有问题都适合使用动态规划，某些问题可能更适合其他算法（如贪心算法）。

5. 注意事项

识别问题特性：在使用动态规划之前，首先要确认问题是否具有最优子结构和重叠子问题的特性。
状态定义：清晰地定义状态和状态转移方程是动态规划成功的关键。
边界条件：在实现动态规划时，注意处理边界条件，确保算法的正确性。
空间优化：在某些情况下，可以通过优化空间复杂度（如只保留必要的状态）来提高算法的效率。

结论

动态规划是一种强大的算法设计技巧，适用于解决许多复杂问题。通过理解其基本原理、实现方式以及典型问题，开发者可以有效地应用动态规划来优化算法性能。在实际应用中，识别问题特性、定义状态和状态转移方程、处理边界条件等都是成功实现动态规划的关键。