[递归]母牛的故事 C语言做法

解题思路：经过对题目的研究，不难发现前四年是遵循1 2 3 4的规律递增，当到了第五年开始，递增规律发生改变，第五年是在第四年的基础上，因为产下的第二头母牛可以产小牛，所以是4+2=6，用数组表示就是V[n]=V[n-1]+V[n-3] （n为当前年份）。综上，我们只需要对前四年的情况进行设置，从第五年开始进行规律的运算就可以完成本题目
题目优化：在不考虑优化的情况下，对本题目进行编写，会出现时间复杂度过高（运算时间过长）的情况。出现这种情况的原因是在求当年的牛的数量时对前一年的牛的数量进行了运算，也对三年前的牛的数量再运算了一次，忽视了已经在数组中存在的情况，所以通过一个判断语句对数据是否存在进行判断，用来检验是否已经存在该数目，来减少运算的次数。

注意：本题目运用的是多次输入的情况，需要在主函数中加一个循环语句来应对多次输入的情况

参考代码:

#include<stdio.h>

int n;
int v[60];

int dfs(int n)
{
	if (v[n]) return v[n];//记忆优化
	if (n < 5) return v[n] = n; 

	return v[n] = dfs(n - 1) + dfs(n - 3);
}

int main()
{
	while (1)
	{
		scanf("%d", &n);
		if (n == 0) break;

		int res = dfs(n);
		printf("%d\n", res);
	}

	return 0;
}