一、动态规划的空间优化为什么重要
动态规划（DP）是算法设计中解决复杂问题的利器，但它的空间复杂度常常让人头疼。比如经典的斐波那契数列问题，如果直接用递归，时间复杂度会爆炸；而用动态规划，虽然时间降到了线性，但空间仍然是O(n)。这时候，空间优化就显得尤为重要了。
想象一下，你在处理一个大规模数据问题，比如路径规划或者文本匹配，如果每个状态都存下来，内存可能瞬间被吃光。这时候，滚动数组和状态压缩就能派上用场了。
二、滚动数组：让空间复杂度降维
滚动数组的核心思想是：只保留当前计算所需的状态，丢弃无用的历史数据。比如斐波那契数列，我们只需要前两个数就能算出当前的数，根本不需要保存整个数组。
示例1：斐波那契数列（Python实现）
def fibonacci(n):
if n <= 1:
return n
# 初始状态：fib(0)=0, fib(1)=1
prev, curr = 0, 1
for i in range(2, n + 1):
# 计算当前值，并更新前两个状态
next_val = prev + curr
prev, curr = curr, next_val
return curr
# 测试
print(fibonacci(10)) # 输出：55
注释：
prev和curr分别代表fib(i-2)和fib(i-1)。- 每次迭代只需计算
next_val = prev + curr，然后更新状态。 - 空间复杂度从O(n)降到了O(1)。
适用场景
- 状态转移仅依赖前几个状态的DP问题（如斐波那契、爬楼梯问题）。
- 数据规模极大，但计算过程只需最近几个值的情况。
三、状态压缩：用位运算优化空间
状态压缩通常用于DP问题的状态可以用二进制表示的情况。比如经典的“旅行商问题”（TSP），我们可以用二进制数表示哪些城市已经访问过，从而大幅减少存储开销。
示例2：旅行商问题（Python实现）
def tsp(dist):
n = len(dist)
# dp[mask][u] 表示从城市u出发，访问过mask对应城市的最小成本
dp = [[float('inf')] * n for _ in range(1 << n)]
dp[1][0] = 0 # 初始状态：从城市0出发，只访问过城市0
for mask in range(1 << n):
for u in range(n):
if not (mask & (1 << u)):
continue # 当前mask未访问过u，跳过
for v in range(n):
if mask & (1 << v):
continue # 已经访问过v，跳过
new_mask = mask | (1 << v)
dp[new_mask][v] = min(dp[new_mask][v], dp[mask][u] + dist[u][v])
# 最终返回从城市0出发，访问所有城市后回到城市0的最小成本
return min(dp[(1 << n) - 1][u] + dist[u][0] for u in range(n))
# 测试
dist = [
[0, 10, 15, 20],
[10, 0, 35, 25],
[15, 35, 0, 30],
[20, 25, 30, 0]
]
print(tsp(dist)) # 输出：80（最优路径：0 -> 1 -> 3 -> 2 -> 0）
注释：
mask是一个二进制数，每一位表示是否访问过对应城市。dp[mask][u]存储的是当前状态的最小成本。- 通过位运算
mask | (1 << v)快速更新状态。
适用场景
- 状态可以用二进制表示的问题（如子集问题、棋盘覆盖问题）。
- 需要高效存储和查询状态的问题。
四、实战应用与注意事项
1. 应用场景
- 路径规划：如最短路径、机器人导航。
- 文本处理：如编辑距离、最长公共子序列。
- 游戏AI：如棋盘类游戏的胜负判断。
2. 技术优缺点
- 滚动数组：
- 优点：大幅降低空间复杂度，代码简洁。
- 缺点：仅适用于状态转移依赖有限前驱的问题。
- 状态压缩：
- 优点：能处理复杂状态表示问题。
- 缺点：代码实现较复杂，对位运算要求高。
3. 注意事项
- 边界条件：DP问题的初始状态和终止状态要仔细处理。
- 状态表示：确保压缩后的状态能唯一标识问题。
- 性能权衡：空间优化可能增加时间常数，需根据实际需求选择。
五、总结
动态规划的空间优化是算法优化的重要技巧。滚动数组适合状态转移简单的问题，而状态压缩则能处理更复杂的场景。实际应用中，我们需要根据问题特点选择合适的优化方法，同时注意边界条件和性能权衡。
评论