递推概述
递推是按照一定的规律来计算序列中的每个项，通常是通过计算前面的一些项来得出序列中的指定项的值。其思想是把一个复杂的庞大的计算过程转化为简单过程的多次重复，以初始（起点）值为基础，用相同的运算规律，逐次重复运算，直至运算结束。简单来说就是找规律，根据规律总结出递推公式，然后计算递归公式的第项。作为题目的答案。
在算法题目中，我们经常遇到此类问题，解决方案包括构造等差等比数列、奇偶项或分情况讨论、利用数和第二类
数的结论等。
一般数列构造
来看一个简单的场景：一天，有五位同学参加了植树活动，他们完成植树的棵树都不相同。问第一位同学植了多少棵时，他指着旁边的第二位同学说比他多植了两棵；追问第二位同学，他又说比第三位同学多植了两棵；... 如此，都说比另一位同学多植两棵。最后问到第五位同学时，他说自己植了10棵。问：到底第一位同学植了多少棵树？
那么很显然这就是个数列，设第一位同学植树的棵树为a1,欲求a1，需从第五位同学植树的棵数a5入手，根据“多两棵”这个规律，按照一定顺序逐步进行推算，即：计算，很显然后一项等于前一项加2，编写程序如下：
#include <iostream>
using namespace std;
int main()
{
int trees_last = 10;
for (int i = 4; i > 0; i--)
trees_last += 2;
cout << trees_last;
return 0;
}
一维线性递推
上楼梯是一个经典的递推问题，楼梯有 阶，上楼可以一步上一阶，也可以一步上二阶。要求编一个程序，计算到
阶共有多少种不同的走法。初看这是个十分复杂的问题，要从
阶计算
阶和
阶，对于
阶，再计算
和
阶；对于对于
阶，再计算
和
阶，如此往复...
不妨转换一下思路，对于递推问题，我们只需要关心某一项与相邻项的关系。记为上到第
阶的可能种数，那么如何上到第
阶呢，只有两种可能，从第
阶或者第
阶上来。
也就是说，
#include<iostream>
using namespace std;
int main()
{
long long n, lay[93];
cin >> n;
lay[1] = 1, lay[2] = 2;
for (int i = 3; i <= n; ++i)
{
lay[i] = lay[i - 1] + lay[i - 2];
}
cout << lay[n] << endl;
return 0;
}
其实你可能已经发现了，这就是个斐波那契数列，在日后我们可能还会遇到很多于此相关的问题。
线性状态递推
我们在数学试卷上也可能见到类似的问题（，一只蜜蜂在下图所示的数字蜂房上爬动,已知它只能从标号小的蜂房爬到标号大的相邻蜂房,现在问你：蜜蜂从蜂房 开始爬到蜂房
，
，且
，则有多少种爬行路线？
输入输入
记
#include<iostream>
using namespace std;
int main()
{
long long m,n, room[93];
cin >> m >> n;
room[1] = 1, room[2] = 2;
for (int i = 3; i <= n-m; ++i)
{
room[i] = room[i - 1] + room[i - 2];
}
cout << room[n-m] << endl;
return 0;
}
许多递推问题很像模拟问题，比如“数的计算”问题：给出正整数 ，按如下方式构造数列：
- 只有一个数
的数列是一个合法的数列。
- 在一个合法的数列的末尾加入一个正整数，但是这个正整数不能超过该数列最后一项的一半，可以得到一个新的合法数列。
请你求出，一共有多少个合法的数列。两个合法数列 不同当且仅当两数列长度不同或存在一个正整数
，使得
。
拿到一道递归题，我们就像做上一个题一样，先手撕一个小样例找找规律。记为
时的可能种数，考察
与
。
可以看出，对于而言，
，进一步地，我们可以猜想，当
为偶数时，存在递推式
。下作简要证明：当
为偶数时，
为正整数，可以成为新的合法数列的一项，
，
为奇数时，
不为正整数，所以得
项为新的合法数列的一项，即
，代回即得
，故命题得证。偶数项的情况得出了，下面我们看奇数项。
显然
有了这些推断，那么这就是个奇偶数列求项问题。
#include<iostream>
using namespace std;
int main()
{
int n, a[1001];
cin >> n;
a[1] = 1, a[2] = 2;
for (int i = 3; i <= n; ++i)
{
if (i % 2 == 0)
a[i] = a[i - 1] + a[i / 2];
else
a[i] = a[i - 1];
}
cout << a[n] << endl;
return 0;
}
双重数列递推
考察“覆盖墙壁”问题。你有一个长为 宽为
的墙壁，给你两种砖头：一个长
宽
，另一个是 L 型覆盖
个单元的砖头。
砖头可以旋转，两种砖头可以无限制提供。你的任务是计算用这两种来覆盖
注意可以使用两种砖头混合起来覆盖，给定
这题的难点在于“基本状况”的寻找，记为仅考虑(a)，
时的可能种数，则
就是题给
的墙壁被全部覆盖的情况。有两种情况可以达到
，如下：
那么麻烦的是还有"L"形砖头，怎么办？不妨记
所以
那么有
#include<iostream>
using namespace std;
const int mod = 10000;
int a[1000002], b[1000002];
int main()
{
int n;
cin >> n;
a[0] = 1;
a[1] = b[1] = 1;
for (int i = 2; i <= n; i++)
{
a[i] = ((a[i - 1] + a[i - 2]) % mod + 2 * b[i - 2] % mod) % mod;
b[i] = (b[i - 1] + a[i - 1]) % mod;
}
cout << a[n];
return 0;
}
组合数学应用
在递推问题中，有许多较难、在短时间内解决的问题。但幸运的是，我们有几个成熟的模型可以应用于这些问题。
卡特兰数（Catalan Number）是组合数学的计数问题中较为常见的一个数列。传统的定义为在平面直角坐标系中，从原点出发，每次只能向上走或者向右走，且不能越过这条直线（可以碰到），求走到
的不同路径的数量。通过推导得到的卡特兰数的通项公式为：
。这个推导过程比较复杂，我们不做要求。
证明如下：由定义知每一步可以是向上走一个单位（记为U）或向右走一个单位（记为R），因此到达
需要恰好
- 总的路径数：首先，如果不考虑任何限制条件，从
到
步中选择
。
- 排除非法路径：接下来，我们需要从这些总路径中去除那些越过了
直线的路径。对于任意一条非法路径，它必定会在某个点第一次越过
，那么在这之前的路径必须是从
到
的路径。由于这种变换是一一对应的，所以非法路径的数量就等于从
- 计算非法路径数：从
步，其中一步已经在初始位置
。
- 合法路径数：最后，合法路径的数量就是总路径数减去非法路径数，即
- 简化公式：利用组合数的性质
，我们可以进一步简化上述表达式。注意到
，我们有
这与卡特兰数的标准形式一致。至此定理得证。
卡特兰数的数列特征十分明显，当看到答案具有这样的规律时，要敏锐的察觉到这就是卡特兰数。我们将通过一个实例来直观的推出卡特兰数的形式：过
个不同点可以构造多少颗二叉树？
为了找规律，我们开始逐级考虑。
- 当
时，显然有且只有1棵树。
- 当
时，第1个点可以向左扩展，使第2个点成为其左子树；同理，第1个点可以向右扩展，使第2个点成为其右子树。
n=1和n=2的情况 - 当
时，
种情况，另外可以让其它2两点分别作为第3个点的左和右子树，为1种情况，共计5种。
n=3的情况 - 依次继续递推即可，画图可知
时有13种情况。
那么这就是个妥妥的卡特兰数列了，套公式计算即可，这里需要注意的是，这里的每一项需要比原始卡特兰数列延后一项。
#include <iostream>
using namespace std;
long long factorial(int n)
{
if (n == 0 || n == 1)
return 1;
long long result = 1;
for (int i = 2; i <= n; ++i) {
result *= i;
}
return result;
}
long long catalanNumber(int n)
{
return factorial(2 * n) / (factorial(n + 1) * factorial(n));
}
int main() {
int n;
cin >> n;
cout << catalanNumber(n + 1) << endl;
return 0;
}
