斐波那契数列 记忆化递归 题解 题目描述 给定多组测试数据，每组输入一个整数 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';
    }
}

#include<bits/stdc++.h>
using namespace std;
#define int long long
/* 斐波那契数列是指这样的数列：数列的第一个和第二个数都为接下来每个数都等于前面 个数之和。
  1:fq(1)第一个数
  2：fg(1)=1 fg(2)=1 fg(n)=fg(n-1)+fg(n-2)可以来个记忆化搜索 本题有t组 
*/
const int N=1e6;
int a[N];
int m,t;
int fg(int t)
{
  if(t==1||t==2) return a[t]=1;
  else return a[t]=fg(t-1)+fg(t-2);//一定要有上一步操作 	
}
signed main()
{ std::ios::sync_with_stdio(0);
  cin.tie(0),cout.tie(0);
  cin>>m;
  while(m--)
  {
    cin>>t;
	cout<<fg(t)<<"\n"; 	
  }	
	return 0;
}