记忆化搜索

求 Fibonacci 第 $i$ 项的深搜程序如下：

int f(int x) {
    if (x <= 2) return 1;
    return f(x - 1) + f(x - 2);
}

该程序直观，但运行效率低. 以 $f(7)$ 为例，列出函数调用情况：

随着 $n$ 的增大，$f(n)$ 的时间复杂度呈指数级增长. 我们发现，有很多函数被重复调用. 使用「记忆化搜索」可避免此情况.

建立数组 $F$ 保存计算结果.

• 若 $f(x)$ 未被调用过，算出 $f(x)$ 的值，并存入 $F[ x]$
• 若 $f(x)$ 已被调用过，直接返回 $F[ x]$

int F[];
F[1] = F[2] = 1;
int f(int x) {
    if (F[x] != 0)  // 若 F[x] 有值，则说明 f(x) 被调用过
        return F[x];
    return F[x] = f(x - 1) + f(x - 2); // 返回时保存
}

记忆化搜索的时间复杂度与动态规划相当，但效率略低. 若动态规划难以设计，则可以采用该算法.