F(1) = 1,F(2) = 2,F(3)= 3, F(4)= 4，
从第4年后（即第五年），大母牛生的小母牛开始可以生小牛，F(5)=F(4)+F(2),即F(n)= F(n-1)+F(n-3),意思为去年的牛数量+可以生小牛的牛的数量=现在的数量
由于又多组数据，可以直接打表，打表的时间复杂度为O(n)（n为表长），加Q次查询，时间复杂度为O(n+Q).

3 参考代码

/*
 * 详解：https://blog.csdn.net/qq_33375598/article/details/104607549
 */
#include <cstdio>

const int MAXN = 60;
int ans[MAXN]= {0,1,2,3};

int main(int argc, char const *argv[]){
    int n;
    for (int i = 4; i < 55; ++i) {//打表
        ans[i] = ans[i-1] + ans[i -3];//去年的牛+出生后的牛生的小牛
    }
    while(scanf("%d", &n) != EOF){
        printf("%d\n", ans[n]);
    }
    return 0;
}

import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int[] numbers=new int[85];
        numbers[1]=1;
        numbers[2]=2;
        numbers[3]=3;
        numbers[4]=4;
        while(sc.hasNext()){
            int n=sc.nextInt();
            for(int i=5;i<85;i++){
                numbers[i]=numbers[i-1]+numbers[i-3];
            }
            System.out.println(numbers[n]);
        }
    }
}

	//水题



	#include <stdio.h>



	voidDataInit(long*a);



	int main()



	{



	    long a[55] = {0, 1, 2, 3};



	    int n, i;



	    DataInit(a);



	    while(scanf("%d", &n)!=EOF)



	    {



	        printf("%ld\n", a[n]);



	    }



	    return0;



	}



	 



	voidDataInit(long*a)



	{



	    int i;



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



	    {



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



	    }



	}

python解法

关键是找到递推公式a[n]=a[n-1]+a[n-3]

import sys

def cowCountAtSomeYear(n):
    arr=[1,2,3,4]
    while len(arr)<n:
        arr.append(arr[-1]+arr[-3])
    return arr[n-1]


for i in sys.stdin.readlines():
    print(cowCountAtSomeYear(int(i)))

public class Solution {
    // dp 定义: dp[i] 表示第i年有多少头牛
    // 初始化: dp[1] = dp[2] = dp[3] = dp[4] = 1;
    // 递推式: dp[i] = dp[i-1] + dp[i-3] (当前的牛数量 = 去年的牛数量 + 可以生小牛的牛数量)
    // 前三年的牛有 dp[i-3],这些牛包括了成熟的母牛(每年生一头),也包括了未成熟的小牛（它们在第四年可以生一头牛）
    // 所以把这两部分累加起来，也就是这dp[i-3]头牛可以在第i年生 dp[i-3]头
    // 可以结合这个例子理解一下: F(5) = F(4) + F(2)；画个图好理解一点
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int[] dp = new int[60];
        dp[1] = dp[2] = dp[3] = dp[4] = 1;

        for (int i = 5; i < dp.length; i++) {
            dp[i] = dp[i - 1] + dp[i - 3];
        }

        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int a = in.nextInt();
            System.out.println(dp[a]);
        }
    }
}

#include <stdio.h>

int main()
{
    int a[56],b[56],ans[56];  //a表示新生的，b表示能生的
    a[1]=0;b[1]=1;ans[1]=1;
    for(int i=2;i<56;i++)
    {
        b[i]=b[i-1];
        if(i>3)
            b[i]+=a[i-3];
        a[i]=b[i];
        ans[i]=ans[i-1]+a[i];
    }
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        printf("%d\n",ans[n]);
    }
    return 0;
}

解题思路：
话不多说，典型的递推规律题，我们先计算几个结果:
注：（老母牛代表n ≥ 4）

    老母牛    初生    2年    3年    总数

第1天 1 0 0 0 1
第2天 1 1 0 0 2
第3天 1 1 1 0 3
第4天 1 1 1 1 4
第5天 2 2 1 1 6
第6天 3 3 2 1 9
————————————————
版权声明：本文为CSDN博主「hestyle」的原创文章，遵循 CC 4.0 BY 版权协议，转载请附上原文出处链接及本声明。
原文链接：https://hestyle.blog.csdn.net/article/details/104626984

#include <iostream>
using namespace std;

int main(int argc, const char * argv[]) {
    //建立一张表，用于f(n)各项值,需要使用long long类型，否则会产生溢出
    long long fTable[56] = {0, 1, 2, 3};
    //注意数组下标从0开始，而计算从1开始
    for (int i = 4; i < 56; ++i) {
        fTable[i] = fTable[i - 1] + fTable[i - 3];
    }
    int number = 0;
    //scanf返回值为正确输入数据的变量个数，当一个变量都没有成功获取数据时，此时返回-1
    while (scanf("%d", &number) != - 1) {
        printf("%lld\n", fTable[number]);
    }
    return 0;
}

//这么多类似斐波那契数列的题？
#include <stdio.h>
#include <stdlib.h>
 
int main()
{
    //c0记录可以产子的牛，c1,c2,c3记录养了1，2天的牛
    long long int c0[55] = {1, 1, 1, 2, 3}, c1[55] = {0, 1, 1, 1, 2}, c2[55] = {0, 0, 1, 1, 1};
    long long int sum[55] = {1, 2, 3, 4, 6};
    int n;
    int start = 5;
    while(~scanf("%d", &n))
    {
        if(n > start)
        {
            for(int i = start; i < n; i++)
            {
                c0[i] = c2[i-1] + c0[i-1];
                c2[i] = c1[i-1];
                c1[i] = c0[i-1];
                sum[i] = c0[i] + c1[i] + c2[i];
            }
            start = n;
        }
        printf("%ld\n", sum[n-1]);
    }
}

#include<iostream>
(720)#include<vector>
using namespace std;
/*
题目问到n年一共有多少头牛，一般而言，要算牛总数，需要算每年生产的牛数，最后累加即可
每年生产的牛数即为当年的成牛数
dp[i]=dp[i-1]+dp[i-3];
*/
int main() {
	int n;
	vector<int> dp(3, 1); //前3年都只有一个成年母牛可以生育，每年都生一个
	for (int i = 3; i < 56; i++) {
		dp.push_back(dp[i - 1] + dp[i - 3]);
	}
	vector<int> sum;
	sum.push_back(1);    //最初的母牛
	for (int i = 1; i < 56; i++) {
		sum.push_back(sum[i - 1] + dp[i - 1]);
	}
	while (cin >> n) {
		cout << sum[n - 1] << endl;
	}

}

import java.util.*;
public class Main{
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int N = 56;
        long[] f = new long[N];
        f[1] = 1;
        f[2] = 2;
        f[3] = 3;
        f[4] = 4;
        for (int i = 5; i < N; i++) {
            f[i] = f[i - 1] + f[i - 3];
        }
        while (input.hasNext()) {
            int n = input.nextInt();
            System.out.println(f[n]);

        }
    }
}

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int[] a=new int[56];
        a[1]=1;
        a[2]=2;
        a[3]=3;
        for(int i=4;i<a.length;i++)
            a[i]=a[i-1]+a[i-3];
        while(sc.hasNext()){
            int c=sc.nextInt();
            System.out.println(a[c]);
        }
    }
}

var func = function (n) {
    let res = [0, 1, 2, 3]
    if (res.indexOf(n) !== -1)
        return res[n]
    for (let i = 4; i <= n; i++) {
        res.push(res[i - 1] + res[i - 3])
    }
    return res[n]
}

var func = function (n) {
    let res = [null, 1, 2, 3, null]
    if (res.indexOf(n) !== -1)
        return res[n]
    for (let i = 4; i <= n; i++) {
        res[4] = res[1] + res[3]
        ;[res[1], res[2], res[3]] = [res[2], res[3], res[4]]
    }
    return res[4]
}

import java.util.Scanner;

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

    public static int f1(int n) {
        if (n == 0){
            return 0;
        }
        int[] a = new int[n+1];
        if (n == 1){
            return 1;
        }else if (n == 2){
            return 2;
        }else if (n == 3){
            return 3;
        }else {
            a[1] = 1;
            a[2] = 2;
            a[3] = 3;
            for (int i = 4;i <= n; i++) {
                a[i] = a[i-1] + a[i-3];
            }
            return a[n];
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNextInt()) {
            int n = sc.nextInt();
            System.out.println(f1(n));
        }
        sc.close();
    }

    /**复杂度过高
    public static int f(int n) {
        if(n == 1){
            return 1;
        }else if(n == 2){
            return 2;
        }else if (n == 3){
            return 3;
        }else {
            return f(n-1) + f(n-3);
        }
    }
     **/
}

其实题目是有错误的，按照他的说法V[0] 应该是 两头？
不过递推公式的思路是没有错的。
#include <iostream>
#include <vector>
using namespace std;
/*
有一头母牛，它每年年初生一头小母牛。每头小母牛从第四个年头开始，每年年初也生一头小母牛。请编程实现在第n年的时候，共有多少头母牛？
*/
int main()
{
    vector<long long> v(56);
    long long temp;
    v[0] = 1;// D
    v[1] = 2;// D A
    v[2] = 3;// D A B 
    v[3] = 4;// D A B C
    v[4] = 6;// D A B C D D A

    for (int i = 4; i < 56; i++)
    {
        v[i] = v[i - 1] + v[i - 3];
    }
    int n;
    while (cin >> n)
    {
        cout << v[n-1] << endl;
    }
}

	import java.util.Scanner;



	public class Main{



	    public static void main(String args[]){



	        Scanner sc = new Scanner(System.in);



	        while(sc.hasNext()){



	            intn = sc.nextInt();



	            inta[] = new int[n+3];



	             



	            a[1] = 1;



	            a[2] = 2;



	            a[3] = 3;



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



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



	            }



	            System.out.println(a[n]);



	        }



	        sc.close();



	    }



	}

public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in); while (scanner.hasNext()) { int n = scanner.nextInt(); int a[] = new int[100];
        a[1] = 1;
        a[2] = 2;
        a[3] = 3;
        a[4] = 4; if (n 4) {
            System.out.println(n);
        } else { for (int i = 5; i <= n; i++) {
                a[i] = a[i - 1] + a[i - 3];
            }
            System.out.println(a[n]);
        }
    }
}