第 28 课：递推算法
递推算法在数学领域可用于求等差数列、等比数列第 n 项的值，也可以用于计算几何图形的划分方式数量；在金融领域可用于复利计算，算出存入本金 P 元钱若干年后应得的本息和；在生物领域，可用于计算种群增长规模；在建筑设计领域，可用于解决铺瓷砖问题，提前计算在地面铺设瓷砖等工作时所需材料的数量，以节约成本。
递推算法在很多行业都已经崭露头角，但究竟什么是递推算法呢？这个知识点还能用于求解哪些领域的问题呢？让我们一起来了解并学习一下。
28.1 递推算法的概念
递推算法是一种处理问题的重要方法。它通过对问题的分析，找到问题相邻项之间的关系（递推式），然后从起点出发（首项或者末项），使用循环不断地迭代，得到最后需要的结果。
设定场景
举个通俗点的例子。已知蛙蛙可以一次蹦一个台阶，也可以一次蹦两个台阶。现在蛙蛙想知道自己蹦到第 n 个台阶，一共有多少种方法。
提炼基础情况
首先，我们需要从问题描述中提炼出一些有用的信息。
当 n = 1 时，蛙蛙只能蹦一个台阶来到终点，所以来到第 1 个台阶时只有这 1 种方法。
当 n = 2 时，蛙蛙可以从地面一次蹦两个台阶来到第 2 个台阶，这是 1 种方法；还可以从地面先到第 1 个台阶，再从第 1 个台阶蹦一个台阶来到第 2 个台阶，所以一共有 1 + 1 = 2 种方法。
也就是当 n = 1 时，有 1 种方法；当 n = 2 时，有 2 种方法。这是递推的起点。
建立递推关系
那当 n > 2 时，该如何处理呢？
比如当 n = 3 时，到达第 3 个台阶的方法可以分为两类：一是从第 1 个台阶直接蹦两个台阶来到第 3 个台阶（具体操作是，先蹦一个台阶来到第 1 个台阶，再蹦两个台阶来到第 3 个台阶）；二是可以先来到第 2 个台阶，再从第 2 个台阶蹦一个台阶来到第 3 个台阶（到达第 2 个台阶的方法前面已经说过，是 2 种，再从第 2 个台阶蹦一个台阶到第 3 个台阶，所以一共有 2 × 1 = 2 种方法）。所以一共有 1 + 2 = 3 种方法。
当 n = 4 时，同理，要想来到第 4 个台阶，可以从第 2 个台阶蹦两个台阶，也可以从第 3 个台阶蹦一个台阶。到达第 2 个台阶有两种方法，到达第 3 个台阶有 3 种方法，所以一共是 2 + 3 = 5 种方法。
总结递推规律
设到达第 n 个台阶的方法数为 f(n) 种，经过上述推论，我们可以得出 f(n) = f(n - 1) + f(n - 2)，其中 n ≥ 3，这就是一个递推公式。
我们得到 n = 1 和 n = 2 情况下的基础值，然后利用递推公式就可以推出第 n 个台阶的方法数。比如要计算到达第 6 个台阶的方法数，就可以逐步从前面往后推。现在已经知道 f(3) 为 3，f(4) 为 5，那么 f(5) = f(4) + f(3) = 5 + 3 = 8，那么 f(6) = f(5) + f(4) = 8 + 5 = 13。
纪要
通过上述描述，我们提炼出递推的三要素：一是找到初始条件（基础项），二是找到递推公式（通过公式，利用基础项往后推导出所有项），三是找到终止条件（指递推的范围，比如递推到第 n 项）。
28.2 实例讲解
例 1：斐波那契数列
对于斐波那契（Fibonacci）数列，已知：f(1) = 1，f(2) = 1，从第三项开始满足公式 f(i) = f(i - 1) + f(i - 2)。输入一个整数 n（1 ≤ n ≤ 20），求 f(n) 的值。
【输入格式】输入一行，一个整数 n。
【输出格式】输出一行，斐波那契数列第 n 项的值。
【输入样例】5
【输出样例】5
解析
按照我们刚刚所描述的三要素，可分为以下几个步骤进行求解。
先确定问题的目标：求得斐波那契数列第 n 项的数值。
找到初始条件，初始条件为前两项，题目中已经给出，分别为：f(1) = 1，f(2) = 1。
找到递推公式，题目中也已给出，从第 3 项开始，满足如下规律：f(i) = f(i - 1) + f(i - 2)，即当前项由前两项之和构成。
根据题目给出的 f(1) 和 f(2) 推出 f(3)，再按照顺序由 f(2) 和 f(3) 推出 f(4)，以此类推，循环到第 n 项即可。
参考代码
#include <iostream>
using namespace std;
int main()
{
int n, f, f1, f2; // 其中 f 表示当前项，f1 和 f2 为当前项的前面两项
cin >> n;
f1 = f2 = 1; // 初始条件，此时 f1 和 f2 就是前面两项，均为 1
for (int i = 3; i <= n; i++) // 从第 3 项开始，最终所求为第 n 项
{
f = f1 + f2; // 当前项为前面两项之和
f1 = f2; // 更新第 1 项
f2 = f; // 更新第 2 项
}
cout << f;
return 0;
}例 2：昆虫繁殖
蛙蛙经常在田野里玩耍，某天他偶然间发现了一种特殊的昆虫，这种昆虫的繁殖能力很强。每对成虫过 x 个月产 y 对卵，每对卵要过 3 个月后才能长成成虫。假设每个成虫不死，第一个月有一对成虫，蛙蛙想知道，到第 z 个月后能有多少对成虫。
【输入格式】输入一行，用空格隔开的整数 x、y、z。
【输出格式】输出一行，1 个整数，即第 z 个月昆虫的数量。
【输入样例 1】1 2 8
【输出样例 1】9
【输入样例 2】3 2 10
【输出样例 2】9
【数据范围】对于 100% 的数据，1 ≤ x ≤ 20，1 ≤ y ≤ 20，z ≤ 50（其中 x < z）。
解析
通过之前的题目解析，蛙蛙已经知道该如何解这种题目了。首先需要找初始条件，你认为初始条件是什么呢？
非常棒，就是第一个月有一对成虫。假设第 n 个月的成虫对数为 F[n]，那么 F[1] = 1，其中前面的 1 表示第一个月，后面的 1 表示已有的第一对成虫。
实际上，前 x 个月的成虫数量都为 1，卵的数量都为 0。
递推公式应该是什么呢？
蛙蛙继续思考：第 n 个月的成虫可以分为两部分，一部分是上个月就有的，由于成虫不会死，所以它们会累加到这个月，即 F[n - 1] 要累加到 F[n]；还有一部分是从卵长大后变成成虫的，卵要想长到成虫，需要经过三个月，也就是说新增的成虫对数就是三个月前卵的对数 f[n - 3]，这里用 f 表示卵的对数。
所以成虫对数就等于 F[n - 1] + f[n - 3]。
那么问题又来了，卵的数量又该如何去求呢？
聪明的你应该从题目中提取出有用信息了，已知每对成虫过 x 个月产 y 对卵，所以卵的数量等于 x 个月之前的成虫数量乘上 y，即 f[n] = F[n - x] × y。
参考代码
#include <iostream>
using namespace std;
long long F[55], f[55]; // F[i] 表示第 i 个月的成虫对数，f[i] 表示第 i 个月新增的虫卵对数
int main()
{
int x, y, z;
cin >> x >> y >> z;
// 前 x 个月成虫还没开始产卵，所以成虫对数一直为 1，卵的对数为 0
for (int i = 1; i <= x; i++)
{
F[i] = 1;
f[i] = 0;
}
for (int i = x + 1; i <= z; i++)
{
// 新增的卵的对数
f[i] = F[i - x] * y;
// 当前成虫对数
F[i] = F[i - 1] + f[i - 3];
}
cout << F[z];
return 0;
}例 3：蛙蛙爬楼梯
经过一段时间的练习，蛙蛙已经能一次蹦上 3 个台阶了，他现在来到一处楼梯前，准备蹦到楼梯顶。
已知楼梯共有 n（1 ≤ n ≤ 50）个台阶。由于蛙蛙最多可以蹦上 3 个台阶，所以他现在可以选择蹦一个台阶，也可以选择蹦 2 个台阶或 3 个台阶，问：蹦到楼梯顶的方法一共有多少种？
【输入格式】输入一行，一个正整数 n，表示这个楼梯的总台阶数量。
【输出格式】输出一行，表示蹦到楼梯顶一共有多少种方法。
【输入样例】4
【输出样例】7
解析
这个问题我们可以直接套公式。还记得第一步要干什么吗？
是的，要先找初始条件。我们用 f[n] 表示蛙蛙跳到第 n 阶楼梯的所有方法。
蛙蛙蹦到第 1 阶楼梯的方法只有 1 种，所以 f[1] = 1；蛙蛙蹦到第 2 阶楼梯的方法有 2 种，一是可以一阶一阶跳，二是可以两阶跳，所以 f[2] = 2；蛙蛙蹦到第 3 阶楼梯的方法有 4 种，分别是一阶一阶一阶跳、一阶两阶跳、两阶一阶跳、三阶跳，所以 f[3] = 4。
第一个步骤已经完成了，第二个步骤自然是要去找递推公式了。
已知蛙蛙最多蹦 3 阶楼梯，所以要想蹦到第 4 阶楼梯，则可以从第 1 阶楼梯跳 3 阶，也可以从第 2 阶楼梯跳 2 个台阶或者从第 3 阶楼梯跳 1 个台阶，这三种情况都能到达第 4 阶楼梯，还有其他可能吗？
自然没有啦！就这几种情况，所以 f[4] = f[1] + f[2] + f[3]，也就是到达当前楼梯的所有方法数为到达前面 3 阶的方法数之和，即 f[n] = f[n - 1] + f[n - 2] + f[n - 3]。
参考代码
#include <iostream>
using namespace std;
long long f[55];
int main()
{
int n;
cin >> n;
// 初始条件
f[1] = 1;
f[2] = 2;
f[3] = 4;
// 从第 4 项开始递推，一直递推到第 n 项
for (int i = 4; i <= n; i++)
{
// 递推公式
f[i] = f[i - 1] + f[i - 2] + f[i - 3];
}
cout << f[n];
return 0;
}例 4：毕业信活动
毕业之际，蛙蛙的班级举行了一个活动，活动要求每个人写一封信给班里的所有同学，然后将信排成一排。每位学生挑选一封其他同学写的信，所有的学生都不能挑选自己写的那封信。
蛙蛙想知道所有人都不拿到自己的信有多少种不同的情况，你能帮帮他吗？
【输入格式】输入一行，一个整数 n，表示班级人数。
【输出格式】输出一行，一个整数，表示所有的情况数。
【输入样例】4
【输出样例】9
【数据范围】对于 100% 的数据，1 ≤ n ≤ 20。
解析
开始时，信的编号和学生编号相对应，即编号相同为自己写的信，如表 6-1 所示。
表 6-1 开始时信的编号与学生的编号
| 1 | 2 | 3 | 4 | 5 | 6 | … | n | |
|---|---|---|---|---|---|---|---|---|
| 信的编号 | 1 | 2 | 3 | 4 | 5 | 6 | … | n |
| 学生编号 | 1 | 2 | 3 | 4 | 5 | 6 | … | n |
假设编号为 1 的同学先取信，可供选择的信有 n - 1 种情况（自己的那封信不能选）。
无论选择哪封信，都属于以下两种情况之一。
自己那封信没有与剩余的任意一封信的位置互换，那么只使用了一封信。剩余的问题就是：其余 n - 1 位学生，选剩下 n - 1 封信，即 f[n - 1]。
自己那封信与剩余的某一封信的位置互换了，此时会有 2 封信被使用。剩余的问题就是：其余 n - 2 位学生，选剩下 n - 2 封信，即 f[n - 2]。表 6-2 是一种情况，即 1 号学生和 3 号学生的信交换，交换后还剩下 n - 2 封信。
表 6-2 1 号学生和 3 号学生的信交换
| 1 | 2 | 3 | 4 | 5 | 6 | … | n | |
|---|---|---|---|---|---|---|---|---|
| 信封编号 | 3 | 2 | 1 | 4 | 5 | 6 | … | n |
| 学生编号 | 1 | 2 | 3 | 4 | 5 | 6 | … | n |
于是可得出递推式：f[n] = (n - 1) × (f[n - 1] + f[n - 2])。
如果这个班里只有一位学生，选一封信的话，必然是自己写的那封，所以没得选，即 f[1] = 0。如果这个班里只有两位学生，那么这两位学生的信必然要交换，只有这一种情况，即 f[2] = 1。所以初始条件为：f[1] = 0，f[2] = 1。
参考代码
#include <iostream>
using namespace std;
long long f[25];
int main()
{
int n;
cin >> n;
// 初始条件
f[1] = 0;
f[2] = 1;
// 从第 3 项开始递推，一直递推到第 n 项
for (int i = 3; i <= n; i++)
{
// 递推公式
f[i] = (i - 1) * (f[i - 1] + f[i - 2]);
}
cout << f[n];
return 0;
}