数据结构与算法 / 系统课时
在记忆化与递推表间转换
在记忆化与递推表间转换
记忆化搜索和递推表不是两套算法,而是同一状态转移的两种执行顺序。本篇用一个递推关系同时实现两种版本,并从访问范围、调用栈和常数开销判断何时该互换。
学习目标
- 保持状态定义不变,在记忆化搜索与递推表之间转换
- 比较两种实现的访问范围、栈空间和常数开销
- 根据依赖关系判断递推表的正确计算顺序
两种写法共享同一状态
设状态 dp(i) 表示第 i 个问题的答案,并满足 dp(i)=dp(i-1)+dp(i-2)。无论采用递归还是循环,状态含义、初始条件和转移关系都不应改变,真正变化的是状态被求值的顺序。
记忆化搜索从目标状态开始向依赖项递归,第一次算出状态后缓存结果;递推表则先确定依赖方向,从初始状态开始按顺序填表。转换时如果连状态含义也一起修改,很容易把实现差异误当成算法差异。
下面用 Fibonacci 状态演示两种等价实现。程序会同时计算多个输入,并验证两种写法得到相同结果。
from functools import lru_cache
def fib_memo(n: int) -> int:
@lru_cache(maxsize=None)
def dp(i: int) -> int:
# 初始状态决定递归停止位置。
if i < 2:
return i
return dp(i - 1) + dp(i - 2)
return dp(n)
def fib_table(n: int) -> int:
if n < 2:
return n
table = [0] * (n + 1)
table[1] = 1
# 依赖更小下标,因此按下标递增即可保证依赖已经就绪。
for i in range(2, n + 1):
table[i] = table[i - 1] + table[i - 2]
return table[n]
for n in (0, 1, 7, 10):
print(n, fib_memo(n), fib_table(n))预期输出
0 0 0
1 1 1
7 13 13
10 55 55从记忆化改成递推表
转换的关键不是把递归机械地改成 for,而是先找出依赖方向。上例中 dp(i) 只依赖更小的下标,因此可以从 0、1 开始递增计算。如果一个状态依赖右侧或更大的下标,循环方向就可能需要反过来。
可以按以下顺序转换:
- 保留原来的状态含义和返回值。
- 把递归终止条件改写成表中的初始值。
- 根据转移式画出“当前状态依赖哪些状态”。
- 选择一种保证依赖先于当前状态完成的遍历顺序。
- 将递归调用替换为已经计算好的表项。
记忆化版本中“调用哪个状态”由递归自然决定;递推版本必须显式设计计算顺序,这也是转换时最容易出错的地方。
从递推表改回记忆化
反向转换时,可以把表中每一个待计算单元重新理解成一个函数参数。表的初始项变成递归终止条件,填表公式变成递归调用,最后为函数增加缓存即可。
例如递推式使用 table[i - 1] 和 table[i - 2],记忆化版本就调用 dp(i - 1) 和 dp(i - 2)。如果原递推只需要最终答案,记忆化函数同样可以只暴露目标状态,不必预先计算所有下标。
选择哪一种实现
| 维度 | 记忆化搜索 | 递推表 |
|---|---|---|
| 状态访问 | 通常只计算从目标可达的状态 | 通常按设计范围主动填表 |
| 调用栈 | 递归深度较大时可能占用较多栈空间 | 循环实现通常没有递归栈 |
| 常数开销 | 有函数调用和缓存查询成本 | 数组访问和循环常数通常更小 |
| 实现难度 | 转移天然写成递归时更直观 | 计算顺序明确时更直接 |
| 空间优化 | 缓存通常保留已访问状态 | 更容易根据依赖窗口压缩空间 |
如果状态空间很大,而目标只会触达其中一部分,记忆化搜索往往能避免无用计算;如果依赖顺序清晰、状态基本都会访问,递推表通常更节省调用开销,也更方便做空间压缩。两者转换时始终先固定“状态是什么、依赖谁”,再改变求值顺序。