采用了记忆化策略，设置了一个记忆点，在输入的所有的n都小于10^6的情况下，可以节省一点点计算量

#include <iostream>
using namespace std;
const int MOD=1e9+7;
int A[1000000];//申请足够大的空间
int p=1;//记忆点，当前数组所计算到的最远的位置
int fib(int n)
{
    if(n>p)//如果当前的fib(n)并未算出,则需要迭代计算
    {
        for(int i=p+1;i<=n;i++)
        {
           A[i]=(A[i-1]+A[i-2])%MOD;
        }
        p=n;//更新记忆点，防止重复计算
    }
    return A[n];
}
int T,n;

int main()
{
    A[0]=0;A[1]=1;//fib(0)和fib(1)单独初始化
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        printf("%d\n",fib(n));
    }
}

可以直接使用动态规划完成。

#include <stdio.h>
const int mod = 1000000007;
const int N = 1000000;
int fib[N + 10];
void init()
{
    fib[1] = 1;
    for (int i = 2; i <= N; ++i)
        fib[i] = (fib[i - 1] + fib[i - 2]) % mod;
}
int T, n;
int main()
{
    init();
    scanf("%d", &T);
    while (T--) scanf("%d", &n), printf("%d\n", fib[n]);
}

当然使用递归+记忆化用数组存储的方式也是可以的。

#include <stdio.h>
const int mod = 1000000007;
const int N = 1000000;
int fib[N + 10];
int fibo(int n)
{
    if (n == 1 || n == 0) return fib[n] = n;
    if (fib[n]) return fib[n];
    else return fib[n] = (fibo(n - 1) + fibo(n - 2)) % mod;
}
int T, n;
int main()
{
    scanf("%d", &T);
    while (T--) scanf("%d", &n), printf("%d\n", fibo(n));
}