数据结构与算法 / 系统课时

在记忆化与递推表间转换

在记忆化与递推表间转换

记忆化搜索和递推表不是两套算法,而是同一状态转移的两种执行顺序。本篇用一个递推关系同时实现两种版本,并从访问范围、调用栈和常数开销判断何时该互换。

学习目标

  • 保持状态定义不变,在记忆化搜索与递推表之间转换
  • 比较两种实现的访问范围、栈空间和常数开销
  • 根据依赖关系判断递推表的正确计算顺序

两种写法共享同一状态

设状态 dp(i) 表示第 i 个问题的答案,并满足 dp(i)=dp(i-1)+dp(i-2)。无论采用递归还是循环,状态含义、初始条件和转移关系都不应改变,真正变化的是状态被求值的顺序。

记忆化搜索从目标状态开始向依赖项递归,第一次算出状态后缓存结果;递推表则先确定依赖方向,从初始状态开始按顺序填表。转换时如果连状态含义也一起修改,很容易把实现差异误当成算法差异。

下面用 Fibonacci 状态演示两种等价实现。程序会同时计算多个输入,并验证两种写法得到相同结果。

python
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))

预期输出

text
0 0 0
1 1 1
7 13 13
10 55 55

从记忆化改成递推表

转换的关键不是把递归机械地改成 for,而是先找出依赖方向。上例中 dp(i) 只依赖更小的下标,因此可以从 0、1 开始递增计算。如果一个状态依赖右侧或更大的下标,循环方向就可能需要反过来。

可以按以下顺序转换:

  1. 保留原来的状态含义和返回值。
  2. 把递归终止条件改写成表中的初始值。
  3. 根据转移式画出“当前状态依赖哪些状态”。
  4. 选择一种保证依赖先于当前状态完成的遍历顺序。
  5. 将递归调用替换为已经计算好的表项。

记忆化版本中“调用哪个状态”由递归自然决定;递推版本必须显式设计计算顺序,这也是转换时最容易出错的地方。

从递推表改回记忆化

反向转换时,可以把表中每一个待计算单元重新理解成一个函数参数。表的初始项变成递归终止条件,填表公式变成递归调用,最后为函数增加缓存即可。

例如递推式使用 table[i - 1] 和 table[i - 2],记忆化版本就调用 dp(i - 1) 和 dp(i - 2)。如果原递推只需要最终答案,记忆化函数同样可以只暴露目标状态,不必预先计算所有下标。

选择哪一种实现

维度 记忆化搜索 递推表
状态访问 通常只计算从目标可达的状态 通常按设计范围主动填表
调用栈 递归深度较大时可能占用较多栈空间 循环实现通常没有递归栈
常数开销 有函数调用和缓存查询成本 数组访问和循环常数通常更小
实现难度 转移天然写成递归时更直观 计算顺序明确时更直接
空间优化 缓存通常保留已访问状态 更容易根据依赖窗口压缩空间

如果状态空间很大,而目标只会触达其中一部分,记忆化搜索往往能避免无用计算;如果依赖顺序清晰、状态基本都会访问,递推表通常更节省调用开销,也更方便做空间压缩。两者转换时始终先固定“状态是什么、依赖谁”,再改变求值顺序。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

在记忆化与递推表间转换

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通