母牛的故事(hdoj 2018,动态规划递推,详解)

有一头母牛，它每年年初生一头小母牛。每头小母牛从第四个年头开始，每年年初也生一头小母牛。请编程实现在第n年的时候，共有多少头母牛？

Sample Input
2
4
5
0
Sample Output
2
4
6

//本代码为只输入一组数据的答案

//方法1:找规律找出来a[i]=a[i-1]+a[i-3] (ps:我第一次就是这样做出来的)

//方法2:归纳出状态转移方程

//现在解释一下为什么a[i] = a[i - 1] + a[i - 3]

//假如i-1年到i年每变化,则a[i] = a[i - 1]

//可是现在要考虑新的母牛和小牛,

//然后把目光放回i-3年.

//为什么是i-1年?

//i-1年有三种牛:第一种:母牛,,,第二种:这一年刚出生的小牛,,,

//第三种:这一年之前出生的小牛,但是这种牛到了i-3年还是小牛,

//那么毫无疑问,这种青年小牛会在第i年之前成长为母牛,可是

//在i-3到i年间假设青年小牛成长为母牛,那么母牛会马上生仔,但是仔在第i年时肯定也是仔

//所以说青年小牛的仔来不及变成母牛,那么i-3年时x个青年小牛

//到第i年时他会变成x个成年小牛,再带来新的x个幼年小牛

//如果i-3年时k个幼年小牛,到第i年时他会变成k个成年小牛,再带来k个幼年小牛

//(小牛刚成熟就可以马上带来新的!!!)

//而假如i-3年有m个母牛,那么第i年会带来m个幼年小牛

//所以如果i-3年时有x+k+m只牛

//i年时则会又多了x+k+m只小牛

//所以a[i]相对于a[i - 1]多了a[i - 3]只牛

#include<bits/stdc++.h>

#define ll long long

using namespace std;

const ll maxn = ;

ll a[maxn] = {};

int main()

{

    ll n;

    scanf("%lld", &n);

    a[] = ; //第一年一头母牛

    a[] = ;

    a[] = ;

    a[] = ;

    a[] = ; //第二年出生的小牛在第五年变成了母牛,并且马上生出了一只小牛

    for (ll i = ; i <= n; i++)

        a[i] = a[i - ] + a[i - ];

    printf("%lld", a[n]);

}