hdu2018 dp

/*
1~4直接取得；
然后后面的生牛的时候都是前一年的加上一定的数。
从第5年看，第五年出生的牛肯定要加上第四年出生的，然后由于第一个出生的牛开始生小牛，这和
最开始的牛生孩子是一样的，所以+dp[i-3];
*/
#include<stdio.h>
#include<string.h>
int dp[60];
int main()
{
    int i,j,n;
    while(scanf("%d",&n)!=EOF)
    {
        if(!n)break;
        dp[1]=1;
        dp[2]=2;
        dp[3]=3;
        dp[4]=4;
        if(n>=1&&n<=4)
            printf("%d
",dp[n]);
        else
        {
            for(i=4;i<=n;i++)
                dp[i]=dp[i-1]+dp[i-3];
            printf("%d
",dp[n]);
        }
    }
}