C++ 探讨奶牛生子的问题

问题描述

有 $N$ 只奶牛，每个奶牛的繁殖周期为 $M$ 年，每只奶牛出生后第 $1$ 年不生育，第 $2$ 年起每年生下一只小奶牛，小奶牛出生后第 $1$ 年也不能生育，第 $2$ 年起也可以生下一只小奶牛。假设所有的奶牛都没有死亡，请问 $T$ 年后一共有多少只奶牛？

解题思路

本题可以采用递归或者动态规划的方式进行求解。我们可以使用一个数组 $dp$ 来表示第 $i$ 年的奶牛数量，那么 $dp_i$ 与 $dp_{i-1}$ 的关系可以表示为：

$dp_i = dp_{i-1} + dp_{i-M}$

即今年的奶牛数量等于去年的奶牛数量加上 $M$ 年前的所有奶牛的数量。但是需要注意的是，$M$ 年前的奶牛可能已经死亡了，请确保只考虑在 $M$ 年前已经出生并且至今没有死亡的奶牛数量。

代码示例

递归实现

#include <iostream>
using namespace std;

// 奶牛的繁殖周期，每 $M$ 年生育
const int M = 3;

// 递归实现
int countCows(int year) {
    if (year == 1 || year == 2) {
        // 第一年和第二年没有新生的奶牛
        return 1;
    } else if (year < M) {
        // 不足 $M$ 年时，只能计算前几年的生育
        int count = 0;
        for (int i = 1; i < year; i++) {
            count += countCows(i);
        }
        return count + 1;
    } else {
        // 去年的奶牛数量加上 $M$ 年前出生并至今没有死亡的奶牛数量
        return countCows(year - 1) + countCows(year - M);
    }
}

int main() {
    int T = 10;
    cout << countCows(T) << endl;
    return 0;
}

动态规划实现

#include <iostream>
using namespace std;

// 奶牛的繁殖周期，每 $M$ 年生育
const int M = 3;

int main() {
    int T = 10;
    int dp[T+1] = {0};
    // 初始化，第一年和第二年都只有一只奶牛
    dp[1] = 1;
    dp[2] = 1;
    // 递推求解
    for (int i = 3; i <= T; i++) {
        if (i < M) {
            // 不足 $M$ 年时，只能计算前几年的生育
            for (int j = 1; j < i; j++) {
                dp[i] += dp[j];
            }
            dp[i] += 1;
        } else {
            // 去年的奶牛数量加上 $M$ 年前出生并至今没有死亡的奶牛数量
            dp[i] = dp[i-1] + dp[i-M];
        }
    }
    cout << dp[T] << endl;
    return 0;
}