母牛的故事 动态规划解法(也有递归解法）

解题思路:
使用动态规划，先初始化最开始的几年的母牛；然后通过一次循环，算出所有年份的母牛数量（今年的数量等于去年的数量加上3年前的牛数（此时3年前的都成为母牛并能产崽）时间复杂度很低。不用担心超时问题。

然后根据输入输出对应的母牛数量就行。

参考代码:

#include<iostream>

using namespace std;

/*int digui(int n){  //用递归的方法结果也是对的，但是因为复杂度较高，可能会有超时错误 

if(n<=0) return 0;

if(n<=1) return n;

else return digui(n-1)+digui(n-3);

}*/

int main()

{

    int a;

    int num[55]={0,1,2,3,4};  //初始化前几年的奶牛数量 

    for (int i=4;i<55;i++)

    num[i]=num[i-1]+num[i-3]; //i表示年份，去年的数量加上3年前的牛数（此时3年前的都成为母牛并能产崽） 

    while(cin>>a&&a&&a<55)

    {

    cout<<num[a]<<endl;

}

    return 0;

}