学步园

大意略。

思路：记忆化搜索即可。

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <string>
using namespace std;

int d[78];
int n;
bool vis[78];

int dp(int i)
{
	int &ans = d[i];
	if(vis[i]) return ans;
	vis[i] = 1;
	if(i == n || i+1 == n) ans = 1;
	else if(i > n) ans = 0;
	else ans = dp(i+2) + dp(i+3);
	return ans;
}

void solve()
{
	memset(vis, 0, sizeof(vis));
	int ans;
	if(n == 1) ans = 1;
	else if(n == 2) ans = 2;
	else ans = dp(1) + dp(2);
	printf("%d\n", ans);
}

int main()
{
	while(~scanf("%d", &n))
	{
		solve();
	}
	return 0;
}