两种方式求解（递归超时，数组➕循环ac）

解题思路:循环+数组

注意事项:因为数据太大，递归会超时，所以采用数组记录已经计算过的数值
参考代码:

#include<iostream>

using namespace std;

int f(int n){

    if(n==1)return 1;

    if(n==2)return 2;

    return (2*f(n-1)+f(n-2))%32767;

}

int main(){

    int N,n;

    cin>>N;

    while(N--){

        cin>>n;

        cout<<f(n)<<endl;

    }

    return 0;

}

#include<iostream>

using namespace std;

int main(){

    int a[1000005]={0,1,2};

    int N,n;

    for(int i=3;i<1000005;i++){

        a[i]=(2*a[i-1]+a[i-2])%32767;

    }

    cin>>N;

    while(N--){

        cin>>n;

        cout<<a[n]<<endl;

    }

    return 0;    

}