C++ 解法, 执行用时: 2ms, 内存消耗: 388KB, 提交时间: 2020-08-02

#include<iostream>
#include<string>
#include<vector>
using namespace std;
  
string inttostring(string str1,string str2)
{
    int len=str1.size();
    int len1=str2.size();
    int cha=len-len1;
    int flag=0;
    for(int i=len1-1;i>=0;i--)
    {
        if(str1[i+cha]+str2[i]-'0'-'0'+flag>9)
        {
            str1[i+cha]=(str1[i+cha]-'0')+str2[i]+flag-10;
            flag=1;
        }
        else
        {
            str1[i+cha]=(str1[i+cha]-'0')+str2[i]+flag;
            flag=0;
        }
    }
    if(flag==1&&cha>0)
        str1[cha-1]=str1[cha-1]+1;
    if(flag==1&&cha==0)
        str1.insert(0,"1");
    return str1;
}
  
int main(void)
{
    int n;
    cin>>n;
    string dp[n+1];
    dp[0]="1";
    dp[1]="1";
    dp[2]="1";
    dp[3]="2";
    for(int i=4;i<=n;++i)
        dp[i]=inttostring(dp[i-1],dp[i-3]);
    cout<<dp[n];
    return 0;
}

C++ 解法, 执行用时: 2ms, 内存消耗: 396KB, 提交时间: 2020-09-08

#include<iostream>
#include<deque>
using namespace std;

string add(string str1,string str2){
    int takein=0;
    string res(str1.size(),'0');
    for(int i=str1.size()-1;i>=0;i--){
        int temp=str1[i]-'0'+str2[i]-'0'+takein;
        takein=temp/10;
        res[i]=temp%10+'0';
    }
    return res;
}


int main(){
    deque<string> qu;
    string str(100,'0');
    str[str.size()-1]='1';
    qu.push_back(str);
    qu.push_back(str);
    str[str.size()-1]='2';
    qu.push_back(str);
    int N;
    cin>>N;
    for(int i=4;i<=N;i++){
        
        qu.push_back(add(qu.front(),qu.back()));
        qu.pop_front();
    }
    const char* res=qu.back().c_str();
    int index=0;
    while(res[index]=='0'){
        res++;
    }
    cout<<res;
    return 0;
}