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

从递归搜索推导记忆化状态

从递归搜索推导记忆化状态

记忆化搜索最稳妥的推导方式,不是先猜一个 dp 数组,而是先写出能正确表达所有选择的递归函数,再观察哪些调用参数共同决定返回值,并把这组参数作为缓存键。本节用最长公共子序列完整走一遍这个过程。

学习目标

  • 能先用递归函数定义子问题,再从调用参数识别状态维度。
  • 能发现递归调用中的重复状态,并用缓存避免重复计算。
  • 能判断哪些参数必须进入状态,哪些固定上下文或冗余信息不应进入缓存键。

先让递归函数只表达问题

设字符串 a、b 的当前位置分别为 i、j,定义 dfs(i, j) 为 a[i:] 与 b[j:] 的最长公共子序列长度。

如果 a[i] == b[j],当前字符可以共同选入,问题变成 1 + dfs(i + 1, j + 1);如果字符不同,就分别尝试跳过 a[i] 或跳过 b[j],取两种结果中的较大值。任一索引到达字符串末尾时返回 0。

这里最重要的不是公式本身,而是函数签名:在字符串内容固定的前提下,返回值只由 i、j 决定,因此 (i, j) 天然就是状态。

从调用参数识别重复状态

暴力递归展开后,不同分支会多次抵达同一个 (i, j)。一旦某次调用已经算出 dfs(4, 3),以后再次出现相同参数时,继续展开整棵子树就是重复工作。

递归调用到二维记忆化状态的转换

这也是“从递归参数反推 dp 维度”的核心方法:先确认哪些参数会改变未来子问题,再把这些参数组成状态键。像字符串 a、b 在整个求解过程中不变,只是固定上下文,不需要成为额外状态维度。

把状态参数原样缓存

下面的完整程序同时运行暴力递归和记忆化版本。两者使用完全相同的状态定义与转移,只给后者增加缓存,因此适合验证“优化没有改变问题含义”。

python
from functools import lru_cache

a = "abcbdab"
b = "bdcaba"
brute_calls = 0

def brute(i: int, j: int) -> int:
    global brute_calls
    brute_calls += 1

    if i == len(a) or j == len(b):
        return 0
    if a[i] == b[j]:
        return 1 + brute(i + 1, j + 1)

    return max(brute(i + 1, j), brute(i, j + 1))

@lru_cache(maxsize=None)
def memo(i: int, j: int) -> int:
    if i == len(a) or j == len(b):
        return 0
    if a[i] == b[j]:
        return 1 + memo(i + 1, j + 1)

    return max(memo(i + 1, j), memo(i, j + 1))

brute_result = brute(0, 0)
memo_result = memo(0, 0)
cache = memo.cache_info()

print(f"brute={brute_result}, calls={brute_calls}")
print(f"memo={memo_result}, hits={cache.hits}, misses={cache.misses}")

预期输出

text
brute=4, calls=309
memo=4, hits=16, misses=38

hits=16 表示有 16 次调用直接复用了缓存结果。misses=38 对应实际计算过的不同状态数量,而暴力递归共进入了 309 次调用;输入继续变长时,这种差距通常会迅速扩大。

状态维度为什么不能多也不能少

如果漏掉真正影响返回值的参数,两个不同子问题会被错误地当成同一个状态。例如 LCS 只缓存 i 而忽略 j,就无法区分“同一个 a[i:] 与 b 的不同后缀比较”的情况,结果会失真。

反过来,也不要把无关信息塞进状态。假设递归函数额外传入“已经匹配了多少字符”,但返回值定义仍然是“从当前位置还能匹配多少”,这个累计值并不影响未来选择,加入缓存键只会制造更多状态。

对长度分别为 m、n 的两个字符串,合法 (i, j) 状态最多约为 (m + 1)(n + 1),所以记忆化后的时间复杂度为 O(mn),缓存空间为 O(mn),递归调用栈最多再占 O(m + n)。

从递归推导状态时,先问一句“哪些参数相同就一定代表同一个剩余问题”。这组最小参数就是记忆化状态;缓存只是优化手段,正确的状态定义才是动态规划真正的核心。

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

目录与阅读设置

阅读设置

17

记录一个想法

从递归搜索推导记忆化状态

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

登录哪都通