斐波那契数列 记忆化递归 题解 题目描述 给定多组测试数据，每组输入一个整数 n，求斐波那契数列的第 n 项。

斐波那契数列定义：f(1)=1, f(2)=1f(n)=f(n−1)+f(n−2) (n>2) 数据范围：1≤n≤30，多组查询

解题思路 记忆化搜索优化用数组缓存已计算的结果，每个斐波那契数仅计算一次，时间复杂度 O(n)。

#include <bits/stdc++.h>
using namespace std;
#define int long long 
int t,n;
// 全局数组：存储斐波那契数，默认初始化为0，作为记忆化缓存
int f[10086];

// 记忆化递归求斐波那契
int fbnq(int x){
    // 递归边界：f(1)=f(2)=1
    if(x==1||x==2)return f[x]=1;
    // 记忆化核心：已计算过，直接返回缓存值
    if(f[x]!=0)return f[x];
    // 递归计算并缓存结果
    f[x]=fbnq(x-1)+fbnq(x-2);
    return f[x];
}

signed main(){
    // 预处理：提前算出1~10085所有斐波那契数
    fbnq(10085);
    cin>>t;
    // 多组查询，O(1)输出结果
    while(t--){
        cin>>n;
        cout<<f[n]<<'\n';
    }
}