斐波那契数列记忆化递归

斐波那契数列记忆化递归是一种通过递归的方式计算斐波那契数列，并使用记忆化搜索来减少重复计算的方法。在计算过程中，我们会保存已经计算过的斐波那契数，以便在需要时直接使用，避免重复计算。

具体实现步骤如下：
1. 创建一个数组或哈希表，用来存储已经计算过的斐波那契数。
2. 定义一个递归函数（如dfs），接收一个参数x，表示第x个斐波那契数。
3. 在递归函数中，首先判断x是否为1或2，如果是，则直接返回1，这是斐波那契数列的起始数。
4. 接着判断数组或哈希表中是否已经存储了第x个斐波那契数，如果有，则直接返回该数。
5. 如果数组或哈希表中没有存储第x个斐波那契数，则递归调用dfs函数计算第x-1和第x-2个斐波那契数，并将结果存入数组或哈希表中。
6. 最后返回第x个斐波那契数。

下面是一个记忆化递归的实现示例代码：

#include <bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;

const int N = 2e5 + 10;
typedef long long ll;
int n;
int num[N]; //存储搜索过的斐波那契数

int dfs(int x) {
    if (x == 1 || x == 2) {
        num[x] = 1;
        return num[x]; //直接调用搜索过的答案
    }
    if (num[x] != 0) {
        return num[x]; //直接调用搜索过的答案
    } else {
        num[x] = dfs(x - 1) + dfs(x - 2); //计算答案并存储
        return num[x]; //返回答案
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n;
    cout << dfs(n);
    return 0;
}