P4731 养牛场（基础）

解题思路

一头母牛 M 从第 2 年开始，每年春天生 1 头小母牛。小母牛要经历两年的成长才会成熟，成熟以后每年春天也会生 1 头小母牛。题目要求统计第 n 年春天的时候，M 一共有多少头"后代母牛"。

设 f[i] 表示第 i 年春天 M 的后代总数。先写几项：第 1 年 M 还没开始生，f[1]=0；第 2 年 M 生了第 1 头，f[2]=1；第 3 年 M 又生 1 头，f[3]=2。接着把前几项完整列出来：0、1、2、2、3、5、7、10、15、22…… 仔细观察可以发现，从第 4 项开始，每一项都等于它前面的第 1 项加上前面的第 3 项，也就是 f[i] = f[i-1] + f[i-3]。道理是这样的：第 i-3 年出生的那一批小母牛，经历了两年的成长，到第 i 年春天正好都成熟了，它们这一年新添的后代数正好等于第 i-3 年时已有的后代总数 f[i-3]；再加上第 i-1 年就已经存在的 f[i-1] 头，就得到了第 i 年的总数。所以从第 4 项开始用 f[i]=f[i-1]+f[i-3] 一路递推到 n 就可以了。n 最大 20，f[20]=1001，用 long long 保存非常安全。

参考代码

// 养牛场：第n年春季母牛M共有多少头后代母牛，递推 f[i]=f[i-1]+f[i-3]
#include <iostream>
int main(){
  long long f[25];
  int n,i;
  std::cin>>n;
  f[1]=0; f[2]=1; f[3]=2;
  for(i=4;i<=n;i++) f[i]=f[i-1]+f[i-3];  // 满三岁的母牛开始生育
  std::cout<<f[n];
  return 0;
}

复杂度分析

一个循环从第 4 项推到第 n 项，每步只做一次加法，时间 O(n)。空间上用一个长度 25 的 long long 数组，是 O(1)。n 最多 20，循环次数很少，瞬间就能算出答案。