动态规划
动态规划是一种将复杂问题分解为子问题求解的算法思想。
背包问题
0-1 背包
给定一组物品，每个物品有重量和价值，在背包容量限制下选择物品使得总价值最大。
实现
python
def knapsack_01(weights, values, capacity):
n = len(weights)
# dp[i][j] 表示前 i 个物品，容量 j 时的最大价值
dp = [[0] * (capacity + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for j in range(1, capacity + 1):
if weights[i - 1] <= j:
# 选择或不选择第 i 个物品
dp[i][j] = max(
dp[i - 1][j],
dp[i - 1][j - weights[i - 1]] + values[i - 1]
)
else:
dp[i][j] = dp[i - 1][j]
return dp[n][capacity]
# 示例
weights = [2, 3, 4, 5]
values = [3, 4, 5, 6]
capacity = 8
max_value = knapsack_01(weights, values, capacity)
print(f"0-1 背包最大价值: {max_value}") # 10完全背包
每个物品可以选择多次。
实现
python
def knapsack_unbounded(weights, values, capacity):
n = len(weights)
dp = [0] * (capacity + 1)
for i in range(1, capacity + 1):
for j in range(n):
if weights[j] <= i:
dp[i] = max(dp[i], dp[i - weights[j]] + values[j])
return dp[capacity]
# 示例
max_value = knapsack_unbounded(weights, values, capacity)
print(f"完全背包最大价值: {max_value}") # 12序列问题
最长递增子序列
python
def length_of_lis(nums):
if not nums:
return 0
n = len(nums)
dp = [1] * n
for i in range(1, n):
for j in range(i):
if nums[i] > nums[j]:
dp[i] = max(dp[i], dp[j] + 1)
return max(dp)
# 示例
nums = [10, 9, 2, 5, 3, 7, 101, 18]
length = length_of_lis(nums)
print(f"最长递增子序列长度: {length}") # 4最长公共子序列
python
def lcs_length(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 = "abcde"
s2 = "ace"
length = lcs_length(s1, s2)
print(f"最长公共子序列长度: {length}") # 3状态压缩
旅行商问题
python
def tsp(graph):
n = len(graph)
# dp[mask][u] 表示经过 mask 节点，最后到达 u 的最短路径
dp = [[float('inf')] * n for _ in range(1 << n)]
dp[1][0] = 0 # 从节点 0 出发
for mask in range(1, 1 << n):
for u in range(n):
if not (mask & (1 << u)):
continue
for v in range(n):
if mask & (1 << v):
continue
new_mask = mask | (1 << v)
dp[new_mask][v] = min(dp[new_mask][v], dp[mask][u] + graph[u][v])
return dp[(1 << n) - 1][0]
# 示例图（邻接矩阵）
graph = [
[0, 10, 15, 20],
[10, 0, 35, 25],
[15, 35, 0, 30],
[20, 25, 30, 0]
]
min_distance = tsp(graph)
print(f"旅行商最短路径: {min_distance}") # 80