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

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

#include <stdio.h>

int fun(int n, int *cache)
{
    if (n == 1 || n == 2 || n == 3)
    {
        return n;
    }

    if (cache[n] != -1)
    {
        return cache[n];
    }
    cache[n] = fun(n - 1, cache) + fun(n - 3, cache);
    return cache[n];
}

int countCows(int n)
{
    int cache[n + 1];
    for (int i = 0; i <= n; i++)
    {
        cache[i] = -1;
    }
    return fun(n, cache);
}

int main()
{
    int n;
    printf("please enter number: ");
    scanf("%d", &n);
    int totalCows = countCows(n);
    printf("%d year %d number\n", n, totalCows);
    return 0;
}