CP003068 递推题解

这是经典的递推题，测试数据很大，递归会超时。
递归代码（测试点10超2）：

#include<bits/stdc++.h>
#define io freopen("in.txt", "r", stdin), freopen("out.txt", "w", stdout)
#define ll long long
#define ull unsigned long long
using namespace std;
// variables setting
ull n;
// functions(others) defining
ull func(int x)
{
    if(x==1)return 1;
    if(x==2)return 2;
    return func(x-1)+func(x-2);
}
// the program subject
void program()
{
    cin>>n;
    cout<<func(n)<<endl;
}
// the main function
int main()
{
    //io;
    program();
    return 0;
}

递推代码（AC）：

#include<bits/stdc++.h>
#define io freopen("in.txt", "r", stdin), freopen("out.txt", "w", stdout)
#define ll long long
#define ull unsigned long long
using namespace std;
// variables setting
ull n,i;
ull a[1000000]={0,1,2};
// functions(others) defining
// the program subject
void program()
{
    cin>>n;
    for(i=3;i<=n;i++)
    {
        a[i]=a[i-1]+a[i-2];//递推表达式
    }
    cout<<a[n]<<endl;
}
// the main function
int main()
{
    //io;
    program();
    return 0;
}