hdu oj 2018 母牛的故事(暴力递归，记忆化搜索，动态规划）

思路分析：
注：有点绕，建议把n假设为一个确定的数再去理解，比如n=5。
1.老母牛能下崽，因为 （第n年母牛数）=（n-1年母牛数）+ （第n年新出生的母牛数）。
2.第n年新出生的母牛数又等于第n年的老母牛数，所以要求第n年的母牛数目，必须知道n-1年的母牛数目和第n年的老母牛数目。
3.因为4年时间小母牛就变成老母牛，所以
(第n年的老母牛数目) = (第n-3年的老母牛数目) + (第n-3年的小母牛数) = 第n-3年母牛总数。

1.通过以上分析，可以得到暴力递归的表达式: n>4时，count[n] = count[n-1] + count[n-3] 。

#include<iostream>
using namespace std;

int cowCount(int year) {
	
	if (year < 5)
		return year;
	return cowCount(year - 1) + cowCount(year - 3);
}

int main()
{
	int year;

	while (cin >> year && year > 0)
		cout << cowCount(year) << endl;

	return 0;
}

2.记忆化搜索：将已经计算过的数据保存好，以后直接使用，不再重复调用递归

#include<iostream>
#include<vector>
using namespace std;

vector<int> mem;
int cowCount_two(int year) {
	
	if (year < 5)
		return year;
	if (mem[year] != -1)             //已经计算过，直接返回
		return mem[year];
	else 
		mem[year]= cowCount_two(year - 1) + cowCount_two(year - 3);    //没有计算过，递归调用计算，并保存计算的结果(记忆)
	return mem[year];
}

int cowCount(int year) {

	mem = vector<int>(year + 1, -1);
	return cowCount_two(year);
}

int main()
{
	int year;

	while (cin >> year && year > 0)
		cout << cowCount(year) << endl;

	return 0;
}

3.动态规划:迭代完成

#include<iostream>
#include<vector>
using namespace std;

vector<int> mem;

int cowCount_three(int year) {

	if (year < 5)      //避免mem下标赋值越界
		return year;
	mem[1] = 1;
	mem[2] = 2;
	mem[3] = 3;
	mem[4] = 4;
	for (int i = 5; i <= year; i++)
		mem[i] = mem[i - 1] + mem[i - 3];
	return mem[year];
}

int cowCount(int year) {

	mem = vector<int>(year + 1, -1);
	return  cowCount_three(year);
}

int main()
{
	int year;

	while (cin >> year && year > 0)
		cout << cowCount(year) << endl;

	return 0;
}