90分悬赏关注

#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iomanip>
#define ll long long
using namespace std;
//cout<<"Thank god, I'm alive\n";
string f[5005]={"0","1","2"};
//1 2 3 5
string add(string a,string b)
{
    int len1=a.size();
    int len2=b.size();
    int num1[1005]={0};
    int num2[1005]={0};
    int ans[10005]={0};
    string final="";
    for(int i=0;i<len1;i++)
    {
        num1[i]=a[len1-1-i]-'0';
    }
    for(int i=0;i<len2;i++)
    {
        num2[i]=b[len2-1-i]-'0';
    }
    for(int i=0;i<max(len1,len2);i++)
    {
        ans[i]=num1[i]+num2[i];
    }
    ll high=0;
    for(int i=0;i<=max(len1,len2);i++)
    {
        ans[i+1]+=ans[i]/10;
        ans[i]%=10;
        if(ans[i]!=0)
        {
            high=i;
        }
    }
    for(int i=0;i<=high;i++)
    {
        final=char(ans[i]+48)+final;
    }
    return final;
}
int main()
{
    int n;
    cin>>n;
    for(int i=3;i<=n;i++)
    {
        f[i]=add(f[i-1],f[i-2]);
    }
    cout<<f[n];
    return 0;
}