题目 1004: [递归]母牛的故事

类似于斐波那契的解法，规律是a[i] = a[i-1] + a[i-3] (i > 4)，用了记忆化搜所优化时间

#include <cstdio>
#include <cstring>
#define MAXN 60
int a[MAXN];
int dfs(int i)
{
	if(i <= 4)
	{
		return a[i];
	}
	else if(a[i] != 0)
	{
		return a[i];
	}
	else
	{
		return a[i] = dfs(i-1) + dfs(i-3);
	}
}

int main()
{
	memset(a,0,sizeof(a));
	for(int i=1;i<=4;i++)
	{
		a[i] = i;
	}
	int n,k=0;
	while(scanf("%d",&n) && n != 0)
	{
		if(k++ != 0) printf("\n");
		printf("%d",dfs(n));
	}
	return 0;
}