备忘录法

备忘录法（Memoization）是一种通过存储子问题解以避免重复计算的优化技术，属于动态规划的自顶向下实现方式。与传统的递归相比，备忘录法通过牺牲部分空间复杂度（通常为O(n)）将时间复杂度从指数级降低至多项式级。

核心思想[编辑 | 编辑源代码]

备忘录法的核心是“记忆化存储”，其工作流程如下：

在递归调用前检查子问题是否已解决
若已解决则直接返回存储的结果
若未解决则正常计算并存储结果

数学表达为： $T (n) = {\begin{cases} 存储的结果 & 如果存在 \\ 递归计算 + 存储 & 否则 \end{cases}$

与制表法对比[编辑 | 编辑源代码]

备忘录法 vs 制表法（Tabulation）
特性	备忘录法	制表法
方向	自顶向下	自底向上
计算顺序	按需计算	全部计算
空间优化	可惰性初始化	通常需预分配
适用场景	子问题稀疏时更优	需要所有子问题时更优

实现模式[编辑 | 编辑源代码]

以下是Python的通用实现模板：

def memoized_function(n, memo={}):
    # 基础情况处理
    if n in base_cases:
        return base_value
    
    # 检查备忘录
    if n in memo:
        return memo[n]
    
    # 递归计算并存储
    result = some_operation(
        memoized_function(n-1, memo),
        memoized_function(n-2, memo)
    )
    memo[n] = result
    
    return result

经典案例：斐波那契数列[编辑 | 编辑源代码]

问题描述[编辑 | 编辑源代码]

计算第n个斐波那契数： $F (n) = {\begin{cases} 0 & if n = 0 \\ 1 & if n = 1 \\ F (n - 1) + F (n - 2) & if n > 1 \end{cases}$

原始递归的问题[编辑 | 编辑源代码]

传统递归会产生指数级时间复杂度O(2^n)：

def fib(n):
    if n <= 1:
        return n
    return fib(n-1) + fib(n-2)

调用树示例（n=5）：

备忘录法优化[编辑 | 编辑源代码]

优化后时间复杂度降为O(n)：

def fib_memo(n, memo={0:0, 1:1}):
    if n not in memo:
        memo[n] = fib_memo(n-1, memo) + fib_memo(n-2, memo)
    return memo[n]

执行过程演示[编辑 | 编辑源代码]

输入n=5时的调用顺序： 1. fib_memo(5) 2. → fib_memo(4) + fib_memo(3) 3. → (fib_memo(3) + fib_memo(2)) + (fib_memo(2) + fib_memo(1)) 4. → ((fib_memo(2) + fib_memo(1)) + (fib_memo(1) + fib_memo(0))) + ((fib_memo(1) + fib_memo(0)) + 1)

备忘录状态变化：

调用	memo内容
初始	{0:0, 1:1}
fib_memo(2)	{0:0, 1:1, 2:1}
fib_memo(3)	{0:0, 1:1, 2:1, 3:2}
fib_memo(4)	{0:0, 1:1, 2:1, 3:2, 4:3}
fib_memo(5)	{0:0, 1:1, 2:1, 3:2, 4:3, 5:5}

实际应用场景[编辑 | 编辑源代码]

文本差异比对[编辑 | 编辑源代码]

在实现diff工具时，备忘录法可用于优化最长公共子序列(LCS)计算：

def lcs_memo(X, Y, m, n, memo={}):
    if (m,n) in memo:
        return memo[(m,n)]
    
    if m == 0 or n == 0:
        return 0
    elif X[m-1] == Y[n-1]:
        memo[(m,n)] = 1 + lcs_memo(X, Y, m-1, n-1, memo)
    else:
        memo[(m,n)] = max(
            lcs_memo(X, Y, m-1, n, memo),
            lcs_memo(X, Y, m, n-1, memo)
        )
    return memo[(m,n)]

游戏路径规划[编辑 | 编辑源代码]

在网格游戏中计算从起点到终点的路径数（有障碍物版本）：

def count_paths(grid, i, j, memo={}):
    if (i,j) in memo:
        return memo[(i,j)]
    
    if not is_valid(grid, i, j):
        return 0
    if is_goal(grid, i, j):
        return 1
    
    memo[(i,j)] = count_paths(grid, i+1, j, memo) + count_paths(grid, i, j+1, memo)
    return memo[(i,j)]

进阶优化[编辑 | 编辑源代码]

空间复杂度优化[编辑 | 编辑源代码]

对于某些问题可采用滚动数组技术，例如斐波那契数列只需存储前两个状态：

def fib_optimized(n):
    if n <= 1:
        return n
    
    prev, curr = 0, 1
    for _ in range(2, n+1):
        prev, curr = curr, prev + curr
    return curr

自动备忘录化[编辑 | 编辑源代码]

使用装饰器实现通用备忘录：

from functools import wraps

def memoize(func):
    cache = {}
    
    @wraps(func)
    def wrapper(*args):
        if args not in cache:
            cache[args] = func(*args)
        return cache[args]
    
    return wrapper

@memoize
def factorial(n):
    return 1 if n <= 1 else n * factorial(n-1)