B2064 斐波那契数列——题解

解题思路

预处理前 30 项：f[1]=f[2]=1，之后 f[i]=f[i-1]+f[i-2]。每次询问直接输出数组中的对应项。

复杂度分析

预处理 $O(30)$，每次询问 $O(1)$，空间 $O(30)$。

C++17 参考代码

#include <bits/stdc++.h>
using namespace std;
int f[31];
int main(){
    f[1]=f[2]=1;for(int i=3;i<=30;i++)f[i]=f[i-1]+f[i-2];
    int n;cin>>n;while(n--){int a;cin>>a;cout<<f[a]<<'\n';}
    return 0;
}

#include <bits/stdc++.h> using namespace std; int f[31]; int main(){ f[1]=f[2]=1;for(int i=3;i<=30;i++)f[i]=f[i-1]+f[i-2]; int n;cin>>n;while(n--){int a;cin>>a;cout<<f[a]<<'\n';} return 0; }