#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;
}

请给出解释