题解

#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
int n,f[5010][5010];
void stoh(string s,int h[]){
    h[0]=s.size();
    reverse(s.begin(),s.end());
    for(int i=1;i<=s.size();i++){
        h[i]=s[i-1]-'0';
    }
}
void add(int a[],int b[],int c[]){
    c[0]=max(a[0],b[0]);
    for(int i=1;i<=c[0];i++){
        c[i]+=a[i]+b[i];
        c[i+1]=c[i]/10;
        c[i]%=10;
    }
    if(c[c[0]+1]>0){
        c[0]++;
    }
}
void printh(int h[]){
    for(int i=h[0];i>0;i--){
        cout<<h[i];
    }
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        if(i<=2){
            stoh(to_string(i),f[i]);
        }else{
            add(f[i-1],f[i-2],f[i]);
        }
    }
    printh(f[n]);
    return 0;
}