记忆化

斐波那锲数列

对于斐波那锲数列，递归的实现方式，时间复杂度是 \(O(2^n)\)，是一个指数级别的，

当n稍微大一点，就会超时。

为什么呢？因为重复计算太多。

例题，1201：菲波那契数列

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

ll f(int n) {
    if (n == 1) return 1;
    if (n == 2) return 1;

    return f(n - 1) + f(n - 2);
}

int main() {
    int n;
    cin >> n;

    while (n--) {
        int x;
        cin >> x;

        cout << f(x) << '\n';
    }

    return 0;
}

我们观察这个二叉树，很多都是重复计算的，如果 \(f_{98}\) 只被计算一次，下次用的时候，直接拿取之前的计算结果，那么每个结点，只会给计算 \(1\) 次。这样时间复杂度就会从 \(O(2^n)\) 下降到 \(O(n)\)。

#include <bits/stdc++.h>

using namespace std;

int mem[50], n;

int f(int n) {
    if (n == 1 || n == 2) return mem[n] = 1;

    if (mem[n]) return mem[n];
    return mem[n] = f(n - 1) + f(n - 2);
}

int main() {
    f(20);

    cin >> n;
    while (n--) {
        int a;
        cin >> a;

        cout << mem[a] << '\n';
    }

    return 0;
}

如何加记忆化

带记忆化的递归函数，模板结构如下：

返回类型 dfs(状态参数) {
    if (到达边界) return 边界答案;

    if (这个状态之前算过) return 记忆中的答案;

    计算当前状态答案;

    记录答案;
    return 答案;
}

对于 void类型 的递归函数

如果是 void 类型的递归函数，要先改造成 有返回值类型的递归函数。

void 类型的递归函数，在问题边界的时候，维护一个全局变量，统计答案。

现在，让函数的返回值，直接表示问题的答案，到达问题边界的时候，返回一个数值。

例如，

对于统计方案数的问题，到达问题的边界时，就返回 \(1\)。

对于斐波那锲数列问题，到达问题的边界时 n == 1 || n == 2， 返回的就是 1。