P4732 兔子繁殖（入门）

解题思路

养殖场有 1 对小兔子。小兔子出生后 1 个月就长大，再过 1 个月（也就是出生后满 2 个月）就能生育，以后每个月都能生 1 对小兔子，而且兔子永远不死。问 n 个月过后，一共有多少对兔子。

这是经典的斐波那契数列问题。设 f[i] 表示第 i 个月结束时兔子的总对数。第 1 个月只有最初那 1 对，f[1]=1；第 2 个月它们刚长大还没生，还是 1 对，f[2]=1；第 3 个月大兔子生了 1 对小兔子，一共 2 对，f[3]=2；第 4 个月大兔子再生 1 对，第 3 个月出生的小兔子还没长大，所以 f[4]=3；第 5 个月是 5 对，正好与样例一致。规律很明显：f[i] = f[i-1] + f[i-2]，意思是这个月的兔子对数 = 上个月已有的对数（都还活着） + 上上个月的对数（这些兔子都长大了，这个月每对都生 1 对）。n 最大 40，f[40]=102334155，用 long long 保存不会溢出。边界情况：n=1 或 n=2 时直接输出 1。

参考代码

// 兔子繁殖：n个月后共有多少对兔子，斐波那契数列递推
#include <iostream>
int main(){
  long long f[45];
  int n,i;
  std::cin>>n;
  f[1]=1; f[2]=1;
  for(i=3;i<=n;i++) f[i]=f[i-1]+f[i-2];  // 长大一个月后每个月都能生一对
  std::cout<<f[n];
  return 0;
}

复杂度分析

从第 3 项循环推到第 n 项，每项一次加法，时间 O(n)。空间上用一个长度 45 的数组，是 O(1)。n 最多 40，循环几十次就结束，速度非常快。