求斐波那契数列第 $i$ 项的 递归 程序如下：

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

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

flowchart TD
A(["f(7)"]) --> B(["f(6)"])
A(["f(7)"]) --> C(["f(5)"])
B(["f(6)"]) --> D(["f(5)"])
B(["f(6)"]) --> E(["f(4)"])
D(["f(5)"]) --> F(["f(4)"])
D(["f(5)"]) --> G(["f(3)"])
F(["f(4)"]) --> H(["f(3)"])
F(["f(4)"]) --> I(["f(2)"])
H(["f(3)"]) --> J(["f(2)"])
H(["f(3)"]) --> K(["f(1)"])
G(["f(3)"]) --> L(["f(2)"])
G(["f(3)"]) --> M(["f(1)"])
E(["f(4)"]) --> N(["f(3)"])
E(["f(4)"]) --> O(["f(2)"])
N(["f(3)"]) --> P(["f(2)"])
N(["f(3)"]) --> Q(["f(1)"])
C(["f(5)"]) --> F1(["f(4)"])
C(["f(5)"]) --> G1(["f(3)"])
F1(["f(4)"]) --> H1(["f(3)"])
F1(["f(4)"]) --> I1(["f(2)"])
H1(["f(3)"]) --> J1(["f(2)"])
H1(["f(3)"]) --> K1(["f(1)"])
G1(["f(3)"]) --> L1(["f(2)"])
G1(["f(3)"]) --> M1(["f(1)"])

随着 $n$ 的增大，$f(n)$ 的时间复杂度爆炸式增长。

我们发现，有很多 状态 被重复计算，如 $f(3)$ 被计算了 5 次。「记忆化搜索」可以缓存计算过的状态，使得每个状态最多计算一次。

具体地，通过数组 $F$ 保存计算结果：

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

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

使用记忆化搜索之后，函数的调用情况：

flowchart TD
A(["f(7)"]) --> B(["f(6)"])
A(["f(7)"]) --> C(["f(5) = F[5]"])
B(["f(6)"]) --> D(["f(5)"])
B(["f(6)"]) --> E(["f(4) = F[4]"])
D(["f(5)"]) --> F(["f(4)"])
D(["f(5)"]) --> G(["f(3) = F[3]"])
F(["f(4)"]) --> H(["f(3)"])
F(["f(4)"]) --> I(["f(2)"])
H(["f(3)"]) --> J(["f(2)"])
H(["f(3)"]) --> K(["f(1)"])

记忆化搜索的时间复杂度与 动态规划 相同，但由于递归调用会产生额外开销，导致其效率略低。若动态规划的 状态转移顺序 难以预测，则可采用记忆化搜索求解所有状态值。