记忆化搜索与状态缓存 - NOI提高级教程

📖 算法原理：重叠子问题与空间换时间

在深度优先搜索 (DFS) 和递归中，很多状态会被多次重复计算。例如在计算斐波那契数 $F(5)$ 时，我们必须计算 $F(4)$ 和 $F(3)$；而在计算 $F(4)$ 时，又要计算一次 $F(3)$。这使得朴素递归的时间复杂度达到了恐怖的指数级 $O(2^N)$。

📐 重叠子问题（Overlapping Subproblems）

记忆化搜索通过引入一个全局缓存容器（通常是数组或哈希表）来记录已经求解过的状态。在每次进入递归函数时，首先查表：

缓存命中 (Cache Hit)：若当前状态已被计算过，直接返回保存好的结果，跳过后续所有分支（剪枝）。
缓存未命中 (Cache Miss)：按照正常逻辑继续递归求解，并在计算出最终结果返回前，将其写入缓存容器。

通过这种自顶向下的“空间换时间”优化，可将时间复杂度骤降为线性 $O(N)$！

优化模式：

演示速度：

选择演示模式，并点击"开始演示"或"单步执行"观察递归树的状态展开与剪枝过程。

🌳 Fibonacci F(5) 递归展开与剪枝树图

💾 memo[] 状态表

memo[0]:?

memo[1]:?

memo[2]:?

memo[3]:?

memo[4]:?

memo[5]:?

// 1. 记忆化搜索：查表与写入缓存
int memo[6] = {-1, -1, -1, -1, -1, -1};

int fib(int n) {
    if (n <= 1) return n;
    if (memo[n] != -1) {
        return memo[n]; // 缓存命中！
    }
    memo[n] = fib(n - 1) + fib(n - 2); // 写入缓存
    return memo[n];
}

// 2. 朴素递归：重复求解重叠子问题
int fib(int n) {
    if (n <= 1) return n;
    return fib(n - 1) + fib(n - 2); // 无休止的重复递归
}

📋 递归回溯计算日志