编辑“︁备忘录法”︁

{{Note|本条目是[[动态规划]]系列的核心方法之一，适合已掌握基础递归的读者学习。}}

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

== 核心思想 ==
备忘录法的核心是“记忆化存储”，其工作流程如下：
# 在递归调用前检查子问题是否已解决
# 若已解决则直接返回存储的结果
# 若未解决则正常计算并存储结果

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

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

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

<syntaxhighlight lang="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
</syntaxhighlight>

== 经典案例：斐波那契数列 ==
=== 问题描述 ===
计算第n个斐波那契数：
<math>F(n) = \begin{cases} 
0 & \text{if } n = 0 \\
1 & \text{if } n = 1 \\
F(n-1) + F(n-2) & \text{if } n > 1 
\end{cases}
</math>

=== 原始递归的问题 ===
传统递归会产生指数级时间复杂度O(2^n)：
<syntaxhighlight lang="python">
def fib(n):
    if n <= 1:
        return n
    return fib(n-1) + fib(n-2)
</syntaxhighlight>

调用树示例（n=5）：
<mermaid>
graph TD
    F5 --> F4
    F5 --> F3
    F4 --> F3
    F4 --> F2
    F3 --> F2
    F3 --> F1
    F2 --> F1
    F2 --> F0
</mermaid>

=== 备忘录法优化 ===
优化后时间复杂度降为O(n)：
<syntaxhighlight lang="python">
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]
</syntaxhighlight>

=== 执行过程演示 ===
输入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)

备忘录状态变化：
{| class="wikitable"
! 调用 !! 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)计算：
<syntaxhighlight lang="python">
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)]
</syntaxhighlight>

=== 游戏路径规划 ===
在网格游戏中计算从起点到终点的路径数（有障碍物版本）：
<syntaxhighlight lang="python">
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)]
</syntaxhighlight>

== 进阶优化 ==
=== 空间复杂度优化 ===
对于某些问题可采用滚动数组技术，例如斐波那契数列只需存储前两个状态：
<syntaxhighlight lang="python">
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
</syntaxhighlight>

=== 自动备忘录化 ===
使用装饰器实现通用备忘录：
<syntaxhighlight lang="python">
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)
</syntaxhighlight>

== 复杂度分析 ==
对于典型问题：
* 时间复杂度：O(子问题数量 × 每个子问题时间)
* 空间复杂度：O(子问题数量 + 递归深度)

以斐波那契数列为例：
* 原始递归：O(2^n)时间，O(n)空间（调用栈）
* 备忘录法：O(n)时间，O(n)空间

== 常见误区 ==
1. '''错误初始化'''：忘记设置基础案例的备忘录值
2. '''状态设计不当'''：使用不完整的参数作为备忘录键
3. '''记忆过度'''：存储不需要重复使用的计算结果
4. '''并发问题'''：在多线程环境中使用可变默认参数

{{Warning|Python中默认参数（如memo={}）在函数定义时只创建一次，可能导致不同调用间意外共享状态！}}

== 延伸阅读 ==
* [[动态规划]]的其他实现方法
* [[尾递归优化]]与备忘录法的结合
* [[分支限界法]]中的记忆化应用

[[Category:计算机科学]]
[[Category:数据结构与算法]]
[[Category:动态规划]]