记忆化搜索+递归

#include<bits/stdc++.h>
using namespace std;

long long x[1000]; 
long long fun(int a){
	if(x[a]) return x[a];
	if(a==1||a==0) return 1;
	else return x[a]=fun(a-2)+fun(a-1);
}

int main(){
	int a;
	cin>>a;
	cout<<fun(a);
	return 0;
}