科学家在热带森林中发现了一种特殊的昆虫，这种昆虫的繁殖能力很强。每对成虫过 X X X 个月后开始产卵，每月产 Y Y Y 对卵，每对卵要过两个月长成成虫。
假设每个成虫不死，第一个月只有一对成虫，且卵长成成虫后的第一个月不产卵( 过 X X X 个月产卵)，问过 Z Z Z 个月以后，共有成虫多少对？
0 ≤ X ≤ 20 , 1 ≤ Y ≤ 20 , X ≤ Z ≤ 50 0 \le X \le 20,1 \le Y \le 20,X \le Z \le 50 0≤X≤20,1≤Y≤20,X≤Z≤50
X , Y , Z X,Y,Z X,Y,Z 的数值。
过 Z Z Z 个月以后，共有成虫对数。
1 2 8
37
http://ybt.ssoier.cn:8088/problem_show.php?pid=1312
昆虫繁殖 问题是 算法初学者 在学习 递推专题 时，必定遇到的问题之一。此题对于初学者来说 难度较高，很容易出现题目推着推着，就把各种变量、下标搞混的情况。😵💫
博主在阅读其他人写的题解时，发现这些题解要么解释的非常潦草，难以理解；要么干脆只有代码，没有解释。💦
所以在对本题进行了一定的研究后，博主撰写了此篇题解，希望能在未来帮助更多的小伙伴弄懂本题的递推关系，最后能够手撕本题代码。🧑🏻💻
在博主看来本题的难点主要有 3 个：
首先解决 第一个问题，该如何表示「过了 z 个月」？能否用列表的方式，来清晰的表式每一个月的数据 ？
该问题的关键在于，我们如何表示刚开始的第一个月（初始状态）？是从 0 开始，还是 1 开始 ? 实际上，两种方式都是可以的，列表的方式如下：
| 月份 | 0月 | 1月 | 2月 | 3月 | 4月 | … | z 月 |
|---|---|---|---|---|---|---|---|
| 初始数据 |
| 月份 | 1月 | 2月 | 3月 | 4月 | 5月 | … | z + 1月 |
|---|---|---|---|---|---|---|---|
| 初始数据 |
在本文中，博主选择从第一种方式，即月份下标从 0 开始（原因会在下文分析完问题二、三后阐述）
对于 第二个问题，我们需要通过 模拟 的方式来推出递推方程。
首先，以 x = 1 , y = 2 , z = 4 x = 1, y = 2, z = 4 x=1,y=2,z=4 的情况进行模拟，此条件表示的是：
因为要求解成虫数量，所以比较容易想到的方式是 创建两个数组，一个存储每个月的成虫总数量（数组 c 表示），另一个存储每个月卵的总数量（数组 r 表示）。
在第 0 个月 时，有 1 对成虫，0 对卵，所以 c [ 0 ] = 1 ， r [ 0 ] = 0 c[0] = 1，r[0] = 0 c[0]=1，r[0]=0
| 月份 | 0月 | 1月 | 2月 | 3月 | 4月 |
|---|---|---|---|---|---|
| 每月成虫总数量 c[i] | 1 | ||||
| 每月卵总数量 r[i] | 0 |
过了 1 个月后（1月），成虫开始产卵，所以在 1 月份时，卵的数量为 2，成虫数量仍为 1， c [ 1 ] = 1 ， r [ 1 ] = 2 c[1] = 1，r[1] = 2 c[1]=1，r[1]=2
| 月份 | 0月 | 1月 | 2月 | 3月 | 4月 |
|---|---|---|---|---|---|
| 每月成虫总数量 c[i] | 1 | 1 | |||
| 每月卵总数量 r[i] | 0 | 2 |
过了 2 个月后（2月），此时 1 月产的卵没有长大为成虫，所以成虫数量仍为 1，并且在这个月，成虫又产生了 y = 2 对卵，则此时共有 4 对卵（2 对新产生的卵，2 对为 1 月份仅成长了 1 个月的卵）， c [ 2 ] = 1 , r [ 2 ] = 4 c[2] = 1,r[2] = 4 c[2]=1,r[2]=4
| 月份 | 0月 | 1月 | 2月 | 3月 | 4月 |
|---|---|---|---|---|---|
| 每月成虫总数量 c[i] | 1 | 1 | 1 | ||
| 每月卵总数量 r[i] | 0 | 2 | 4 |
过了 3 个月后（3月），此时 1 月的卵成长为了成虫，成虫数量增加，所以 c [ 3 ] = c [ 2 ] + r [ 3 − 2 ] = 3 c[3] = c[2] + r[3 - 2] = 3 c[3]=c[2]+r[3−2]=3；对于卵来说，此时有 2 只卵变成成虫，但是原先的 1 对成虫又产生了 2 只卵，所以 r [ 3 ] = r [ 2 ] − 2 + 2 = 4 r[3] = r[2] - 2 + 2 = 4 r[3]=r[2]−2+2=4
| 月份 | 0月 | 1月 | 2月 | 3月 | 4月 |
|---|---|---|---|---|---|
| 每月成虫总数量 c[i] | 1 | 1 | 1 | 3 | |
| 每月卵总数量 r[i] | 0 | 2 | 4 | 4 |
于是我们容易总结得到，成虫数量 c [ i ] = c [ i − 1 ] + r [ i − 2 ] c[i] = c[i - 1] + r[i -2] c[i]=c[i−1]+r[i−2] （但是这其实是有问题的 ❌）
我们继续来看 4 月份，如果按照上面这种方式，那么 c [ 4 ] = c [ 3 ] + r [ 4 − 2 ] = 8 c[4] = c[3] + r[4-2] = 8 c[4]=c[3]+r[4−2]=8。
但是仔细思考，2 月份的 4 对卵，已经有 2 对在 3 月份变成了成虫，实际上只有 2 对卵在 4 月份变成了成虫，正确的 c [ 4 ] = c [ 3 ] + 2 = 6 c[4] = c[3] + 2 = 6 c[4]=c[3]+2=6 才对。🤔
经过思考，我们发现上面公式里的 r[i-2]，不应该设成 2 个月前卵的总数量，因为如果是总数量，那么这些卵中有一部分来自于上个月，这部分卵在下一个月就会变成成虫，而不是等 2 个月后才变成成虫。💡
所以，更加合理的表示方式，应该是将「r 数组设置为每个月新增的卵的数量」。✅
即每个月的成虫总数量 c[i]，应该等于 上个月成虫的总数量 c[i-1] + 上 2 个月新增的卵的数量 r[i-2]（其他时间产生的卵和 c[i] 的计算并没有关系）
这也是为什么很多题解中，选择设置 c 为每月成虫总数量，但是 r 为每月新增 的卵的数量的原因。
这样设定变量含义，就能够得到正确的递推方程：
c
[
i
]
=
c
[
i
−
1
]
+
r
[
i
−
2
]
r
[
i
]
=
c
[
i
−
x
]
∗
y
c[i] = c[i - 1] + r[i - 2]\\r[i] = c[i -x] * y
c[i]=c[i−1]+r[i−2]r[i]=c[i−x]∗y
递推方程含义为（在 x 个月之后）：
每月成虫总数量 c [ i ] c[i] c[i] = 上一个月成虫总数量 c [ i − 1 ] c[i -1] c[i−1] + 上 2 个月新增的卵的数量 r [ i − 2 ] r[i - 2] r[i−2]
每月新增的卵的数量 r [ i ] r[i] r[i] = 上 x 个月的成虫总数量 c [ i − x ] ∗ y c[i-x] * y c[i−x]∗y
在 0 - x-1 月，第一对成虫不产卵，
c
[
i
]
≡
1
,
r
[
i
]
≡
0
c[i] \equiv 1,r[i] \equiv 0
c[i]≡1,r[i]≡0，即：
| 月份 | 0月 | 1月 | 2月 | 3月 | 4月 |
|---|---|---|---|---|---|
| 每月成虫总数量 c[i] | 1 | ||||
| 每月卵新增数量 r[i] | 0 |
在 x 月，第一对成虫开始产卵，且产了 y 对卵，
c
[
x
]
=
1
,
r
[
x
]
=
y
c[x] = 1,r[x] = y
c[x]=1,r[x]=y，即：
| 月份 | 0月 | 1月 | 2月 | 3月 | 4月 |
|---|---|---|---|---|---|
| 每月成虫总数量 c[i] | 1 | 1 | |||
| 每月卵新增数量 r[i] | 0 | 2 |
在 x+1 - z 月，递推关系满足上述递推方程，有：
| 月份 | 0月 | 1月 | 2月 | 3月 | 4月 |
|---|---|---|---|---|---|
| 每月成虫总数量 c[i] | 1 | 1 | 1 | 3 | 5 |
| 每月卵新增数量 r[i] | 0 | 2 | 2 | 2 | 6 |
按照样例中
z
=
8
z=8
z=8，我们也可以得到下表，样例答案 c[8] = 37 就是这样来的。
| 月份 | 0月 | 1月 | 2月 | 3月 | 4月 | 5月 | 6月 | 7月 | 8月 |
|---|---|---|---|---|---|---|---|---|---|
| 每月成虫总数量 c[i] | 1 | 1 | 1 | 3 | 5 | 7 | 13 | 23 | 37 |
| 每月卵新增数量 r[i] | 0 | 2 | 2 | 2 | 6 | 10 | 14 | 26 | 46 |
下面，我们以 x = 2 , y = 3 , z = 4 x = 2,y=3,z = 4 x=2,y=3,z=4 为例，再次模拟。
首先，在 0 - x-1 月，第一对成虫是不产卵的，所以
c
[
i
]
≡
1
,
r
[
i
]
≡
0
c[i] \equiv 1,r[i] \equiv 0
c[i]≡1,r[i]≡0，即：
| 月份 | 0月 | 1月 | 2月 | 3月 | 4月 |
|---|---|---|---|---|---|
| 每月成虫总数量 c[i] | 1 | 1 | |||
| 每月卵新增数量 r[i] | 0 | 0 |
在 x 月，第一对成虫开始产卵，且产了 y 对卵，
c
[
x
]
=
1
,
r
[
x
]
=
y
c[x] = 1,r[x] = y
c[x]=1,r[x]=y，即：
| 月份 | 0月 | 1月 | 2月 | 3月 | 4月 |
|---|---|---|---|---|---|
| 每月成虫总数量 c[i] | 1 | 1 | 1 | ||
| 每月卵新增数量 r[i] | 0 | 0 | 3 |
在 x+1 - z 月，递推关系满足上述递推方程，有：
| 月份 | 0月 | 1月 | 2月 | 3月 | 4月 |
|---|---|---|---|---|---|
| 每月成虫总数量 c[i] | 1 | 1 | 1 | 1 | 4 |
| 每月卵新增数量 r[i] | 0 | 0 | 3 | 3 | 3 |
至此，整道题目的逻辑关系基本理清。✅
在梳理完了递推关系后，我们尝试书写代码（这题对于初学者来说确实麻烦，但是对逻辑思维是很好的锻炼）
我们从上面的过程入手，边界条件 就比较容易确定。显然，总过程分为 3 段，分别是 0-x-1月, x月, x+1-z 月，所以我们的程序也可以分为 3 段来写：
//模拟 0 - x - 1 月
for(int i = 0; i <= x - 1; i++){
c[i] = 1;
r[i] = 0;
}
//模拟 x 月
c[x] = 1;
r[i] = y;
//模拟 x + 1 - z 月
for(int i = x + 1; i <= z; i++){
c[i] = c[i - 1] + r[i - 2];
r[i] = r[i - x] * y;
}
这样，我们就完成了本题的核心代码（恭喜 🎉🎉🎉）
其实，在对
x
x
x 月的赋值时，也可以将其合并到第 3 段，但是这个合并操作要求 x > 1（因为第 3 段的 递推方程中包含 r[i - 2]，所以需要保证 i - 2 > 0）。为了代码逻辑更加清晰，博主采用了 3 段式。
当然，博主也看到有代码是月份从 1 开始的，这样的话，「过了 z 个月」就是 z + 1 月，最终输出的答案是 c[z + 1]，这样从 1 开始的下标就可以保证 2、3 段合并时 i − 2 > 0 i - 2 > 0 i−2>0 了，也是可以的。
在本文中，博主选择月份下标从 0 开始，这样「过了 z 个月」就是 z 月，比较容易记忆，大伙可以根据喜好自行选择。
🍉 PS：本题需要使用 long long 类型，int 类型不够用。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e2 + 10;
ll c[N]; //c数组存储每个月成虫的总数量
ll r[N]; //r数组存储每个月新增的昆虫数量
ll x, y, z;
int main() {
cin >> x >> y >> z;
//模拟 0 - x - 1 月
for (int i = 0; i <= x - 1; ++i) {
c[i] = 1;
r[i] = 0;
}
//模拟 x 月
c[x] = 1;
r[x] = y;
//模拟 x + 1 - z 月
for (int i = x + 1; i <= z; ++i) {
r[i] = c[i - x] * y;
c[i] = c[i - 1] + r[i - 2];
}
cout << c[z] << endl;
return 0;
}
