第13章 动态规划
13.1 动态规划核心：状态定义 + 状态转移方程
动态规划（Dynamic Programming，简称DP）是一种通过把原问题分解为相对简单的子问题的方式来求解复杂问题的方法。它的核心思想就是"大事化小，小事化了"。
动态规划的两个关键要素
状态定义：我们需要明确dp[i]、dp[i][j]等状态变量代表什么含义。这是动态规划中最关键也是最难的一步。
状态转移方程：描述当前状态如何从之前的状态转移而来，也就是递推关系式。
动态规划的基本步骤
- 确定状态：明确dp数组的含义
- 确定状态转移方程：找出状态之间的关系
- 确定初始条件和边界情况：设置base case
- 确定遍历顺序：决定计算dp数组的顺序
实例方法表格
| 功能名称 | 实例调用方法 | 具体功能、注意事项、必需参数/可选参数 |
|---|---|---|
| 状态定义 | dp[i] = ... | 定义dp数组每个位置的含义，必须清晰明确 |
| 状态转移 | dp[i] = f(dp[i-1], dp[i-2], ...) | 建立状态间的递推关系，考虑所有可能的转移路径 |
| 初始化 | dp[0] = value; dp[1] = value | 设置基础情况，处理边界条件 |
简单示例：爬楼梯问题
假设你正在爬楼梯，每次可以爬1或2个台阶，问有多少种不同的方法可以爬到第n阶？
python
def climb_stairs(n):
"""
爬楼梯问题的动态规划解法
Args:
n (int): 楼梯的总阶数
Returns:
int: 爬到第n阶的不同方法数
Raises:
ValueError: 当n小于0时抛出异常
"""
# 输入验证
if n < 0:
raise ValueError("楼梯阶数不能为负数")
# 处理边界情况
if n <= 1:
return 1
# 状态定义：dp[i] 表示爬到第i阶的方法数
dp = [0] * (n + 1)
# 初始化基础情况
dp[0] = 1 # 在地面，有一种方法（不动）
dp[1] = 1 # 第1阶，只有一种方法（爬1步）
# 状态转移：dp[i] = dp[i-1] + dp[i-2]
# 因为可以从i-1阶爬1步到达，或者从i-2阶爬2步到达
for i in range(2, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]
return dp[n]
# 测试代码
try:
result = climb_stairs(5)
print(f"爬5阶楼梯有 {result} 种方法") # 输出：8
except ValueError as e:
print(f"输入错误: {e}")这节讲了动态规划的核心概念，包括状态定义和状态转移方程的重要性，并通过爬楼梯这个经典例子展示了动态规划的基本应用模式。
13.2 斐波那契数列与爬楼梯（一维 DP）
斐波那契数列是动态规划最经典的入门例子，它完美体现了动态规划的思想。斐波那契数列定义为：F(0) = 0, F(1) = 1, F(n) = F(n-1) + F(n-2) (n ≥ 2)。
斐波那契数列的动态规划解法
斐波那契数列和爬楼梯问题本质上是同一个问题，只是初始条件略有不同。爬楼梯问题中，f(0) = 1, f(1) = 1，而标准斐波那契是f(0) = 0, f(1) = 1。
空间优化技巧
观察斐波那契数列的状态转移方程，我们发现计算f(n)只需要f(n-1)和f(n-2)两个值，因此不需要保存整个dp数组，只需要保存前两个值即可。
实例方法表格
| 功能名称 | 实例调用方法 | 具体功能、注意事项、必需参数/可选参数 |
|---|---|---|
| 基础DP解法 | fib_dp(n) | 使用O(n)空间存储所有中间结果 |
| 空间优化 | fib_optimized(n) | 只使用O(1)空间，保存最近两个值 |
| 记忆化递归 | fib_memo(n, memo) | 递归+缓存，避免重复计算 |
斐波那契数列实现
python
def fibonacci_basic(n):
"""
斐波那契数列的基础动态规划实现
Args:
n (int): 要计算的斐波那契数列位置
Returns:
int: 第n个斐波那契数
Raises:
ValueError: 当n小于0时抛出异常
"""
if n < 0:
raise ValueError("n不能为负数")
if n <= 1:
return n
# 创建dp数组存储所有中间结果
dp = [0] * (n + 1)
dp[0] = 0
dp[1] = 1
# 填充dp数组
for i in range(2, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]
return dp[n]
def fibonacci_optimized(n):
"""
斐波那契数列的空间优化实现
Args:
n (int): 要计算的斐波那契数列位置
Returns:
int: 第n个斐波那契数
Raises:
ValueError: 当n小于0时抛出异常
"""
if n < 0:
raise ValueError("n不能为负数")
if n <= 1:
return n
# 只保存前两个值，节省空间
prev2 = 0 # f(i-2)
prev1 = 1 # f(i-1)
for i in range(2, n + 1):
current = prev1 + prev2 # f(i) = f(i-1) + f(i-2)
prev2 = prev1 # 更新f(i-2)
prev1 = current # 更新f(i-1)
return prev1
# 测试两种实现
try:
n = 10
result1 = fibonacci_basic(n)
result2 = fibonacci_optimized(n)
print(f"第{n}个斐波那契数（基础DP）: {result1}") # 输出：55
print(f"第{n}个斐波那契数（空间优化）: {result2}") # 输出：55
# 验证爬楼梯问题
stairs_result = climb_stairs(5) # 复用13.1节的函数
fib_result = fibonacci_optimized(6) # 爬5阶对应fib(6)
print(f"爬5阶楼梯方法数: {stairs_result}, fib(6): {fib_result}") # 都是8
except ValueError as e:
print(f"输入错误: {e}")这节深入讲解了斐波那契数列和爬楼梯问题的一维动态规划解法，并介绍了重要的空间优化技巧，将空间复杂度从O(n)降低到O(1)。
13.3 0-1 背包问题与空间优化（滚动数组）
0-1背包问题是动态规划中的经典二维问题。问题描述：给定n个物品，每个物品有重量w[i]和价值v[i]，背包容量为W，求在不超过背包容量的前提下能获得的最大价值。
0-1背包问题的状态定义
对于二维DP，我们定义dp[i][j]表示考虑前i个物品，在背包容量为j的情况下能获得的最大价值。
状态转移方程
对于每个物品i，我们有两个选择：
- 不选择物品i：dp[i][j] = dp[i-1][j]
- 选择物品i（前提是j >= w[i]）：dp[i][j] = dp[i-1][j-w[i]] + v[i]
因此状态转移方程为：dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])
滚动数组优化
观察状态转移方程，我们发现dp[i][j]只依赖于dp[i-1][...]，因此可以用一维数组来优化空间，这就是滚动数组技巧。
实例方法表格
| 功能名称 | 实例调用方法 | 具体功能、注意事项、必需参数/可选参数 |
|---|---|---|
| 二维DP解法 | knapsack_2d(weights, values, capacity) | 使用二维数组，直观易理解 |
| 滚动数组优化 | knapsack_1d(weights, values, capacity) | 使用一维数组，空间复杂度O(W) |
| 背包方案重构 | get_knapsack_solution(...) | 回溯找出具体选择了哪些物品 |
0-1背包问题实现
python
def knapsack_2d(weights, values, capacity):
"""
0-1背包问题的二维动态规划解法
Args:
weights (list): 物品重量列表
values (list): 物品价值列表
capacity (int): 背包容量
Returns:
int: 能获得的最大价值
Raises:
ValueError: 当输入参数无效时抛出异常
"""
# 输入验证
if not weights or not values:
raise ValueError("物品列表不能为空")
if len(weights) != len(values):
raise ValueError("重量和价值列表长度必须相同")
if capacity < 0:
raise ValueError("背包容量不能为负数")
n = len(weights)
# dp[i][j] 表示考虑前i个物品，容量为j时的最大价值
dp = [[0] * (capacity + 1) for _ in range(n + 1)]
# 填充dp表
for i in range(1, n + 1):
for j in range(capacity + 1):
# 不选择第i个物品（注意weights索引是i-1）
dp[i][j] = dp[i - 1][j]
# 如果能选择第i个物品，比较选择和不选择的收益
if j >= weights[i - 1]:
dp[i][j] = max(dp[i][j], dp[i - 1][j - weights[i - 1]] + values[i - 1])
return dp[n][capacity]
def knapsack_1d(weights, values, capacity):
"""
0-1背包问题的滚动数组优化解法
Args:
weights (list): 物品重量列表
values (list): 物品价值列表
capacity (int): 背包容量
Returns:
int: 能获得的最大价值
Raises:
ValueError: 当输入参数无效时抛出异常
"""
# 输入验证
if not weights or not values:
raise ValueError("物品列表不能为空")
if len(weights) != len(values):
raise ValueError("重量和价值列表长度必须相同")
if capacity < 0:
raise ValueError("背包容量不能为负数")
n = len(weights)
# 滚动数组：dp[j] 表示容量为j时的最大价值
dp = [0] * (capacity + 1)
# 注意：内层循环要从后往前遍历
# 这是为了确保dp[j - weights[i]]还是上一轮的值
for i in range(n):
for j in range(capacity, weights[i] - 1, -1):
dp[j] = max(dp[j], dp[j - weights[i]] + values[i])
return dp[capacity]
# 测试背包问题
try:
weights = [2, 3, 4, 5]
values = [3, 4, 5, 6]
capacity = 8
result_2d = knapsack_2d(weights, values, capacity)
result_1d = knapsack_1d(weights, values, capacity)
print(f"背包容量 {capacity} 的最大价值（二维DP）: {result_2d}") # 输出：10
print(f"背包容量 {capacity} 的最大价值（滚动数组）: {result_1d}") # 输出：10
except ValueError as e:
print(f"输入错误: {e}")这节详细讲解了0-1背包问题的动态规划解法，包括二维DP和滚动数组优化，并强调了滚动数组中内层循环必须从后往前遍历的重要细节。
13.4 最长公共子序列（LCS）与编辑距离（二维 DP）
最长公共子序列（LCS）和编辑距离都是经典的二维动态规划问题，它们在字符串处理、生物信息学等领域有广泛应用。
最长公共子序列（LCS）
LCS问题：给定两个字符串text1和text2，找到它们的最长公共子序列的长度。子序列不要求连续，但要求保持相对顺序。
状态定义：dp[i][j]表示text1的前i个字符和text2的前j个字符的LCS长度。
状态转移方程：
- 如果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])
编辑距离
编辑距离问题：给定两个字符串word1和word2，计算将word1转换成word2所需的最少操作次数。操作包括插入、删除、替换一个字符。
状态定义：dp[i][j]表示将word1的前i个字符转换成word2的前j个字符所需的最少操作次数。
状态转移方程：
- 如果word1[i-1] == word2[j-1]：dp[i][j] = dp[i-1][j-1]
- 否则：dp[i][j] = min(dp[i-1][j] + 1, dp[i][j-1] + 1, dp[i-1][j-1] + 1)
实例方法表格
| 功能名称 | 实例调用方法 | 具体功能、注意事项、必需参数/可选参数 |
|---|---|---|
| LCS计算 | lcs_length(text1, text2) | 计算两个字符串的最长公共子序列长度 |
| 编辑距离 | edit_distance(word1, word2) | 计算两个字符串的编辑距离 |
| 方案重构 | get_lcs_sequence(...) | 重构具体的LCS字符串 |
LCS和编辑距离实现
python
def lcs_length(text1, text2):
"""
计算两个字符串的最长公共子序列长度
Args:
text1 (str): 第一个字符串
text2 (str): 第二个字符串
Returns:
int: 最长公共子序列的长度
Raises:
TypeError: 当输入不是字符串时抛出异常
"""
# 输入验证
if not isinstance(text1, str) or not isinstance(text2, str):
raise TypeError("输入必须是字符串")
m, n = len(text1), len(text2)
# dp[i][j] 表示text1[:i]和text2[:j]的LCS长度
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]:
# 字符相同，LCS长度加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]
def edit_distance(word1, word2):
"""
计算两个字符串的编辑距离
Args:
word1 (str): 第一个字符串
word2 (str): 第二个字符串
Returns:
int: 编辑距离（最少操作次数）
Raises:
TypeError: 当输入不是字符串时抛出异常
"""
# 输入验证
if not isinstance(word1, str) or not isinstance(word2, str):
raise TypeError("输入必须是字符串")
m, n = len(word1), len(word2)
# dp[i][j] 表示将word1[:i]转换为word2[:j]的最少操作次数
dp = [[0] * (n + 1) for _ in range(m + 1)]
# 初始化边界条件
for i in range(m + 1):
dp[i][0] = i # 删除所有字符
for j in range(n + 1):
dp[0][j] = j # 插入所有字符
for i in range(1, m + 1):
for j in range(1, n + 1):
if word1[i - 1] == word2[j - 1]:
# 字符相同，不需要操作
dp[i][j] = dp[i - 1][j - 1]
else:
# 字符不同，取三种操作的最小值
# dp[i-1][j] + 1: 删除word1[i-1]
# dp[i][j-1] + 1: 插入word2[j-1]
# dp[i-1][j-1] + 1: 替换word1[i-1]为word2[j-1]
dp[i][j] = min(dp[i - 1][j] + 1, dp[i][j - 1] + 1, dp[i - 1][j - 1] + 1)
return dp[m][n]
# 测试LCS和编辑距离
try:
# LCS测试
text1 = "abcde"
text2 = "ace"
lcs_result = lcs_length(text1, text2)
print(f"'{text1}' 和 '{text2}' 的LCS长度: {lcs_result}") # 输出：3
# 编辑距离测试
word1 = "horse"
word2 = "ros"
edit_result = edit_distance(word1, word2)
print(f"'{word1}' 到 '{word2}' 的编辑距离: {edit_result}") # 输出：3
except TypeError as e:
print(f"类型错误: {e}")这节介绍了两个重要的二维动态规划问题：最长公共子序列和编辑距离，展示了它们在字符串处理中的强大应用能力，并提供了完整的实现代码。