第7章 动态规划
动态规划是一种强大的算法设计技术,用于解决具有重叠子问题和最优子结构性质的问题。动态规划通过保存子问题的解来避免重复计算,将时间复杂度从指数级降低到多项式级。本章将详细介绍动态规划的核心思想和经典应用。
7.1 动态规划基础概念
Fibonacci DP
Fibonacci DP Animation
动态规划的核心思想是将复杂问题分解为简单的子问题,通过求解子问题来构建原问题的解。与分治算法不同,动态规划特别适用于子问题重叠的情况。分治算法会重复求解相同的子问题,而动态规划将子问题的解存储起来,避免重复计算。
动态规划问题具有两个关键性质。最优子结构是指问题的最优解包含子问题的最优解。如果问题的最优解可以通过组合子问题的最优解得到,那么问题具有最优子结构性质。重叠子问题是指在求解过程中,相同的子问题会被多次计算。
def fibonacci_naive(n):
if n <= 1:
return n
return fibonacci_naive(n - 1) + fibonacci_naive(n - 2)
def fibonacci_dp(n):
if n <= 1:
return n
dp = [0] * (n + 1)
dp[0] = 0
dp[1] = 1
for i in range(2, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]
return dp[n]
def fibonacci_optimized(n):
if n <= 1:
return n
prev, curr = 0, 1
for _ in range(2, n + 1):
prev, curr = curr, prev + curr
return curr
import time
n = 35
start = time.time()
result_naive = fibonacci_naive(n)
time_naive = (time.time() - start) * 1000
start = time.time()
result_dp = fibonacci_dp(n)
time_dp = (time.time() - start) * 1000
start = time.time()
result_opt = fibonacci_optimized(n)
time_opt = (time.time() - start) * 1000
print(f"斐波那契数列第{n}项:")
print(f"递归解法: {result_naive}, 时间: {time_naive:.2f}毫秒")
print(f"动态规划: {result_dp}, 时间: {time_dp:.2f}毫秒")
print(f"空间优化: {result_opt}, 时间: {time_opt:.2f}毫秒")
斐波那契数列是理解动态规划的绝佳例子。递归解法的时间复杂度为O(2^n),因为每次调用产生两个新的调用。动态规划解法的时间复杂度为O(n),空间复杂度为O(n)。通过进一步优化,只保存前两个值,空间复杂度可以降低到O(1)。
动态规划有两种实现方式。自顶向下带备忘录的方法使用递归,在递归过程中保存已计算的子问题解。自底向上的方法从最小的子问题开始,逐步构建更大问题的解。自底向上的方法通常更高效,避免了递归调用的开销。
7.2 背包问题
Knapsack DP
Knapsack DP Animation
背包问题是动态规划的经典应用,有多种变体。0-1背包问题是最基础的版本,给定n个物品,每个物品有重量和价值,背包有容量限制。要求选择物品装入背包,使得总重量不超过容量,且总价值最大。每个物品只能选择装入或不装入,不能分割。
def knapsack_01(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(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], dp
weights = [2, 3, 4, 5]
values = [3, 4, 5, 6]
capacity = 5
max_value, dp_table = knapsack_01(weights, values, capacity)
print(f"背包最大价值: {max_value}")
def print_selected_items(weights, values, capacity, dp):
n = len(weights)
w = capacity
selected = []
for i in range(n, 0, -1):
if dp[i][w] != dp[i-1][w]:
selected.append(i-1)
w -= weights[i-1]
print("选择的物品索引:", selected)
print("对应重量:", [weights[i] for i in selected])
print("对应价值:", [values[i] for i in selected])
print_selected_items(weights, values, capacity, dp_table)
背包问题的动态规划解法使用二维数组dp[i][w]表示考虑前i个物品、背包容量为w时的最大价值。状态转移方程为dp[i][w] = max(dp[i-1][w], dp[i-1][w-weights[i-1]] + values[i-1])。如果不选择第i个物品,价值为dp[i-1][w]。如果选择第i个物品,需要从剩余容量中扣除物品重量,价值为dp[i-1][w-weights[i-1]]加上物品价值。
背包问题的时间复杂度为O(n×capacity),空间复杂度为O(n×capacity)。通过观察状态转移方程,可以发现dp[i]只依赖于dp[i-1],因此空间复杂度可以优化到O(capacity)。
def knapsack_01_optimized(weights, values, capacity):
dp = [0] * (capacity + 1)
for i in range(len(weights)):
for w in range(capacity, weights[i] - 1, -1):
dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
return dp[capacity]
完全背包问题允许每种物品选择多次。状态转移方程略有不同,dp[i][w] = max(dp[i-1][w], dp[i][w-weights[i-1]] + values[i-1])。注意这里使用dp[i][w-weights[i-1]]而不是dp[i-1][w-weights[i-1]],因为可以重复选择同一物品。
7.3 最长公共子序列
最长公共子序列(LCS)问题要求找到两个序列的最长公共子序列。子序列是从原序列中删除若干元素后得到的序列,元素相对顺序保持不变。LCS问题在文本比较、DNA序列分析、版本控制等场景有重要应用。
def lcs_length(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], dp
def lcs_sequence(text1, text2, dp):
m, n = len(text1), len(text2)
result = []
i, j = m, n
while i > 0and j > 0:
if text1[i-1] == text2[j-1]:
result.append(text1[i-1])
i -= 1
j -= 1
elif dp[i-1][j] > dp[i][j-1]:
i -= 1
else:
j -= 1
return''.join(reversed(result))
text1 = "ABCBDAB"
text2 = "BDCABA"
length, dp_table = lcs_length(text1, text2)
sequence = lcs_sequence(text1, text2, dp_table)
print(f"字符串1: {text1}")
print(f"字符串2: {text2}")
print(f"LCS长度: {length}")
print(f"LCS序列: {sequence}")
LCS Animation
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])。时间复杂度为O(m×n),空间复杂度为O(m×n)。通过滚动数组优化,空间复杂度可以降低到O(min(m,n))。
LCS问题可以扩展到多个字符串的公共子序列,以及最长递增子序列等变体。最长递增子序列问题要求找到序列中最长的严格递增子序列。
def lis_length(nums):
ifnot nums:
return0
dp = [1] * len(nums)
for i in range(1, len(nums)):
for j in range(i):
if nums[j] < nums[i]:
dp[i] = max(dp[i], dp[j] + 1)
return max(dp)
nums = [10, 9, 2, 5, 3, 7, 101, 18]
print(f"最长递增子序列长度: {lis_length(nums)}")
7.4 编辑距离
编辑距离衡量两个字符串的相似度,定义为将一个字符串转换为另一个字符串所需的最少操作次数。允许的操作包括插入、删除和替换字符。编辑距离在拼写检查、DNA序列比对、机器翻译等场景广泛应用。
def edit_distance(word1, word2):
m, n = len(word1), len(word2)
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][j] = min(
dp[i-1][j] + 1,
dp[i][j-1] + 1,
dp[i-1][j-1] + 1
)
return dp[m][n]
word1 = "kitten"
word2 = "sitting"
distance = edit_distance(word1, word2)
print(f"'{word1}'到'{word2}'的编辑距离: {distance}")
Edit Distance Animation
编辑距离的状态转移方程为,如果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),分别对应删除、插入和替换操作。
7.5 最短路径问题
动态规划也可以用于解决最短路径问题。Floyd-Warshall算法使用动态规划计算所有顶点之间的最短路径,适合稠密图。算法通过逐步考虑中间顶点来更新最短路径。
def floyd_warshall(graph):
n = len(graph)
dist = [[float('inf')] * n for _ in range(n)]
for i in range(n):
for j in range(n):
if i == j:
dist[i][j] = 0
elif graph[i][j] != 0:
dist[i][j] = graph[i][j]
for k in range(n):
for i in range(n):
for j in range(n):
if dist[i][k] + dist[k][j] < dist[i][j]:
dist[i][j] = dist[i][k] + dist[k][j]
return dist
graph = [
[0, 4, 0, 0, 0, 0, 0, 8, 0],
[4, 0, 8, 0, 0, 0, 0, 11, 0],
[0, 8, 0, 7, 0, 4, 0, 0, 2],
[0, 0, 7, 0, 9, 14, 0, 0, 0],
[0, 0, 0, 9, 0, 10, 0, 0, 0],
[0, 0, 4, 14, 10, 0, 2, 0, 0],
[0, 0, 0, 0, 0, 2, 0, 1, 6],
[8, 11, 0, 0, 0, 0, 1, 0, 7],
[0, 0, 2, 0, 0, 0, 6, 7, 0]
]
distances = floyd_warshall(graph)
print("所有顶点之间的最短距离:")
for row in distances:
print([int(d) if d != float('inf') else'INF'for d in row])
Floyd-Warshall Animation
Floyd-Warshall算法的时间复杂度为O(n³),空间复杂度为O(n²)。虽然时间复杂度较高,但算法简单直观,适合小规模图的全面路径分析。
Bellman-Ford算法也是基于动态规划的最短路径算法,它可以处理负权边。算法通过松弛操作逐步更新最短路径估计,最多进行n-1轮迭代。
def bellman_ford(edges, n, start):
dist = [float('inf')] * n
dist[start] = 0
for _ in range(n - 1):
for u, v, w in edges:
if dist[u] != float('inf') and dist[u] + w < dist[v]:
dist[v] = dist[u] + w
for u, v, w in edges:
if dist[u] != float('inf') and dist[u] + w < dist[v]:
return None
return dist
7.6 动态规划的优化技巧
动态规划有多种优化技巧可以提高效率。空间优化通过滚动数组或状态压缩降低空间复杂度。时间优化通过预处理或剪枝减少不必要的计算。状态转移优化通过观察状态转移方程的特殊性质简化计算。
def knapsack_with_value_range(weights, values, capacity):
max_value = sum(values)
min_cost = [float('inf')] * (max_value + 1)
min_cost[0] = 0
for i in range(len(weights)):
for v in range(max_value, values[i] - 1, -1):
if min_cost[v - values[i]] != float('inf'):
min_cost[v] = min(min_cost[v],
min_cost[v - values[i]] + weights[i])
for v in range(max_value, -1, -1):
if min_cost[v] <= capacity:
return v
return0
这个优化版本以价值为状态维度,适合背包容量很大但物品价值范围较小的情况。通过交换状态维度,可以显著降低时间复杂度。
本章我们学习了动态规划的基本思想和经典应用。动态规划通过保存子问题的解避免重复计算,适用于具有最优子结构和重叠子问题性质的问题。斐波那契数列、背包问题、最长公共子序列、编辑距离等都是动态规划的典型应用。理解状态定义和状态转移方程是掌握动态规划的关键。
预览时标签不可点