解题思路

有一对兔子，从第 3 个月起每个月生一对兔子，新兔子长到第 3 个月又开始生。求第 n 个月的兔子总数。

这是一个经典的斐波那契数列问题。

规律：

• 第 1 个月：1 对
• 第 2 个月：1 对
• 第 3 个月：2 对（原来 1 对 + 新生 1 对）
• 第 4 个月：3 对
• 第 5 个月：5 对
• ……

从第 3 个月开始，每月的对数 = 前两个月之和。

为什么？ 因为第 n 个月的兔子 = 上个月的兔子（都还在）+ 这个月新生的兔子，而新生的兔子数是两个月前的兔子数（那些兔子到这个月满 3 个月开始生）。所以 f(n) = f(n-1) + f(n-2)。

注意：

• 第 50 个月的兔子数非常大（超过 10 亿），int 装不下，要用 long long
• 用循环迭代而不是递归，避免递归重复计算太慢

参考代码

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;

    long long a = 1, b = 1, t;

    if (n <= 2) {
        cout << 1;
    } else {
        // 从第 3 个月迭代到第 n 个月
        for (int i = 3; i <= n; i++) {
            t = a + b;  // 本月 = 上月 + 上上月
            a = b;
            b = t;
        }
        cout << b;
    }
    return 0;
}

复杂度分析

• 时间复杂度：O(N)，循环到第 n 个月
• 空间复杂度：O(1)