費氏數列

#include <iostream>
#include <vector>

using namespace std;

long long dp[20000]={};

/*int step(long long n){
    if(n==0) return 1;
    if(n==1) return 1;
    else return step(n-1)+step(n-2);
}*/

int step(long long n){
    if(dp[n-1]==0) step(n-1);
    if(dp[n-2]==0) step(n-2);
    dp[n]=dp[n-1]+dp[n-2];
}

int main()
{
    long long N;
    dp[0]=1;
    dp[1]=1;
    while(cin>>N){
        if(N==1||N==2){
            cout<<dp[N-1]<<endl;
        }else{
            step(N-1);
            cout<<dp[N-1]<<endl;
        }
    }
    return 0;
}