编辑“︁记忆化搜索”︁

{{DISPLAYTITLE:记忆化搜索}}

'''记忆化搜索'''（Memoization）是一种优化递归算法的技术，通过存储已计算的结果来避免重复计算，从而显著提高程序效率。它是[[动态规划]]（Dynamic Programming）的核心思想之一，尤其适用于解决具有重叠子问题特性的问题。

== 概念介绍 ==
记忆化搜索的核心思想是“以空间换时间”。当一个递归算法在解决某个问题时，可能会重复计算相同的子问题多次，导致时间复杂度过高。记忆化搜索通过维护一个缓存（通常是数组或哈希表），在首次计算某个子问题时将结果存储起来，后续再次遇到相同子问题时直接返回缓存结果，从而减少计算量。

=== 适用场景 ===
* 问题可以分解为多个重叠子问题（如斐波那契数列、背包问题）
* 子问题的解会被多次重复使用
* 递归调用中存在大量重复计算

=== 与动态规划的关系 ===
记忆化搜索是动态规划的“自顶向下”实现方式，而传统的动态规划表格填充是“自底向上”的实现。两者本质相同，但记忆化搜索通常更直观，代码更易编写。

== 算法实现 ==
以下以经典的斐波那契数列问题为例，展示普通递归与记忆化搜索的对比。

=== 普通递归实现 ===
普通递归会重复计算大量子问题，时间复杂度为<math>O(2^n)</math>：
<syntaxhighlight lang="python">
def fibonacci(n):
    if n <= 1:
        return n
    return fibonacci(n-1) + fibonacci(n-2)
</syntaxhighlight>

调用树的可视化（以fib(5)为例）：
<mermaid>
graph TD
    A[fib(5)] --> B[fib(4)]
    A --> C[fib(3)]
    B --> D[fib(3)]
    B --> E[fib(2)]
    C --> F[fib(2)]
    C --> G[fib(1)]
    D --> H[fib(2)]
    D --> I[fib(1)]
    E --> J[fib(1)]
    E --> K[fib(0)]
    F --> L[fib(1)]
    F --> M[fib(0)]
</mermaid>

=== 记忆化搜索实现 ===
加入缓存后，时间复杂度降为<math>O(n)</math>：
<syntaxhighlight lang="python">
def fibonacci(n, memo={}):
    if n <= 1:
        return n
    if n not in memo:
        memo[n] = fibonacci(n-1, memo) + fibonacci(n-2, memo)
    return memo[n]
</syntaxhighlight>

=== 输入输出示例 ===
输入：<code>fibonacci(10)</code><br>
输出：<code>55</code><br>
解释：第10个斐波那契数是55，记忆化版本只会计算每个子问题一次。

== 实际应用案例 ==
=== 案例1：网格路径计数 ===
问题描述：在m×n网格中，从左上角到右下角只能向右或向下移动，有多少条独特路径？

记忆化搜索解法：
<syntaxhighlight lang="python">
def uniquePaths(m, n, memo={}):
    if m == 1 or n == 1:
        return 1
    key = (m, n)
    if key not in memo:
        memo[key] = uniquePaths(m-1, n, memo) + uniquePaths(m, n-1, memo)
    return memo[key]
</syntaxhighlight>

=== 案例2：背包问题 ===
0-1背包问题的记忆化搜索实现：
<syntaxhighlight lang="python">
def knapsack(values, weights, capacity, n, memo={}):
    if n == 0 or capacity == 0:
        return 0
    key = (n, capacity)
    if key not in memo:
        if weights[n-1] > capacity:
            memo[key] = knapsack(values, weights, capacity, n-1, memo)
        else:
            memo[key] = max(
                values[n-1] + knapsack(values, weights, capacity-weights[n-1], n-1, memo),
                knapsack(values, weights, capacity, n-1, memo)
            )
    return memo[key]
</syntaxhighlight>

== 性能分析 ==
{| class="wikitable"
|+ 时间复杂度比较
! 算法类型 !! 时间复杂度 !! 空间复杂度
|-
| 普通递归 || <math>O(2^n)</math> || <math>O(n)</math>（调用栈）
|-
| 记忆化搜索 || <math>O(n)</math> || <math>O(n)</math>（缓存+调用栈）
|}

== 实现技巧 ==
1. '''缓存键设计'''：确保缓存键能唯一标识子问题状态，通常使用：
   * 基本类型参数直接组合
   * 复杂对象可以序列化为字符串
   * 多维问题使用元组

2. '''初始状态处理'''：明确递归终止条件

3. '''缓存清理'''：对于大规模问题，可能需要定期清理缓存

== 常见误区 ==
* 混淆记忆化与缓存：记忆化是特定类型的缓存，专为优化递归设计
* 过度记忆化：不是所有递归都需要记忆化，只有存在重叠子问题时才有效
* 状态设计错误：错误的缓存键会导致错误结果

== 扩展阅读 ==
记忆化搜索可以进一步优化为：
* 使用装饰器自动实现记忆化（Python的<code>@functools.lru_cache</code>）
* 转换为迭代式的动态规划实现
* 结合剪枝策略的优化

== 总结 ==
记忆化搜索通过存储子问题解来优化递归算法，是解决重叠子问题的高效技术。理解并掌握这一概念，能显著提升解决复杂算法问题的能力，也是学习动态规划的重要基础。

[[Category:计算机科学]]
[[Category:面试技巧]]
[[Category:搜索算法]]