#include <bits/stdc++.h>
using namespace std;
int n,k;
string dp[5050];
const int maxn = 1000005;
long long a[maxn],b[maxn],c[maxn];
string jieguo;
string add(string A,string B){
    memset(a,0,sizeof(a));
    memset(b,0,sizeof(b));
    memset(c,0,sizeof(c));
    for (int i = 0;i < A.size();i++) a[i] = A[A.size() - i - 1] - '0';
    for (int i = 0;i < B.size();i++) b[i] = B[B.size() - i - 1] - '0';
    int i;
    for (i = 0;i < max(A.size(),B.size());i++){
        c[i+1] = (a[i] + b[i] + c[i]) / 10;
        c[i] = (a[i] + b[i] + c[i]) % 10;
    }
    if (c[i]) i++;
    for (i = i - 1;i >= 0;i--) jieguo += c[i]+'0';
    return jieguo;
}
int main(){
    cin >> n;
    dp[1] = "1",dp[0] = "1",dp[2]= "2";
    for (int i = 3;i <= n;++i){
        dp[i] = add(dp[i-1],dp[i-2]);
    }
    cout << dp[n];
    return 0;
}

请给出解释