[递归]母牛的故事(动态规划，递归)

解题思路:
写出数学表达式 F（x）{  x<=3     f(x)=x;// 前三年只有一头母牛生孩子

                                       x>3      f(x)=f(x-1)+f(x-3)//第 x年 的母牛数量为x =  生的母牛数量+前一年的母牛数量

                                    }
注意事项:使用递归可能时间不够 所以用DP好一点

参考代码:

//DP  最大值运行时间0.004 秒

#include<iostream>

#include<cstdio>

using namespace std;

int main()

{

    int n;

    cin>>n;

    while(n!=0){ 

        int num[10086]={0};

        num[1]=1;num[2]=2;num[3]=3;

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

        {

            num[i]=num[i-3]+num[i-1];

        }

        cout<<num[n]<<endl;

         cin>>n;

    }

    return 0;

}

//递归  最大值运行时间超过一秒

#include<iostream>

#include<cstdio>

using namespace std;

int f(int n)

{

    if(n<=3)

    return n;

    else {

        return f(n-3)+f(n-1);

    }

}

int main()

{

    int n;

    cin>>n;

    while(n!=0){ 

        cout<<f(n)<<endl;

         cin>>n;

    }

    return 0;

}