递推算法（三）：递推式的建立与化简本文是优编程「信息学竞赛重难点算法数据结构专题」第三节「递推算法」的第 3 篇，本节共 5 篇。本篇讲建立递推式的三种方法：从构造过程中找状态并用相邻项作差化简、按关键事件分段计数、分析操作过程得到一阶线性递推并求通项，例题是 NOIP 普及组的数的计算、栈和 Hanoi 双塔问题。适合备战 CSP-J 的同学。
一、本篇导读
递推是用已经算出的小规模结果计算大规模结果的方法，写之前要定好三要素：状态（f[i] 表示什么）、递推式（f[i] 由哪些更小的状态合成）、初始条件与边界（开头几项的值，下标何时越界）。
本节前两篇的题目，状态比较明显，按最后一步分类就能直接写出递推式。本篇三道题需要多想一步：
- 数的计算：状态要从数列的构造过程中找出来，写出的递推式带求和号，需要通过相邻项作差化简。
- 栈：按最后一步分类写不出简单的式子，要找一个关键事件把方案切成两段，用乘法原理建式。
- Hanoi 双塔问题：求的是最少步数，要分析移动过程中哪些步骤必不可少，得到一阶线性递推，再求出通项公式。
二、知识精讲：递推式的建立与化简
2.1 从构造过程中找状态
有些题目描述的是一个逐步构造的过程，例如「在数列末尾不断加数」。找状态的方法是问一句：接下来还能怎样做，只取决于当前局面的哪个量？这个量就是状态。
数的计算中，一个合法数列之后还能接哪些数，只取决于它的最后一项，与前面各项无关，所以状态就是「当前最后一项的值」。确定状态后，再按「下一步加入哪个数」分类，就得到递推式。
2.2 相邻项作差化简
递推式形如 f_{i} = 1 + \sum_{j = 1}^{g(i)}f_{j} 时，每项都要求一次和。把 f_{i} 和 f_{i - 1} 的式子并排写出，比较求和范围：
- 两者求和范围相同，则 f_{i} = f_{i - 1}。
- f_{i} 的求和范围多出若干项，则 f_{i} 等于 f_{i - 1} 加上多出的这几项。
求和号就被消掉了。这个方法在本节第 5 篇的覆盖墙壁中还会用来消去辅助状态。
2.3 分段计数
有些计数题的方案可以按某个关键事件切成前后两段，两段互不影响。设前段有 x 种、后段有 y 种，由乘法原理这一类共 xy 种；再按关键事件发生的位置分类，用加法原理相加。栈就是这样建式的，得到的数列称为卡特兰数（Catalan 数）。
2.4 一阶线性递推求通项
递推式形如 x_{n} = p\, x_{n - 1} + q（p \neq 1）时，两边同时加上常数 \frac{q}{p - 1}，得到
x_{n} + \frac{q}{p - 1} = p\left( x_{n - 1} + \frac{q}{p - 1} \right)
数列 \left\{ x_{n} + \frac{q}{p - 1} \right\} 是公比为 p 的等比数列，通项立即可得。有了通项，可以直接估算答案的位数，判断需要什么数据类型。
三、真题精讲
例 1：数的计算
题意简述
给出正整数 n，按规则构造数列：只有一个数 n 的数列合法；在合法数列末尾加入一个不超过最后一项一半的正整数，得到的新数列也合法。求合法数列的个数，1 \leq n \leq 1000。样例：n = 6 时有 \lbrack 6\rbrack、\lbrack 6,1\rbrack、\lbrack 6,2\rbrack、\lbrack 6,3\rbrack、\lbrack 6,2,1\rbrack、\lbrack 6,3,1\rbrack，输出 6。
思路分析
直观写法是把所有合法数列逐个构造出来计数。构造的数列个数就等于答案，n = 1000 时答案为 1981471878，约 2 \times 10^{9} 个，无法在时限内完成。
按 2.1 节找状态：数列之后能接的数只取决于最后一项。设 f[i] 为「当前最后一项是 i」时，从这里往后能得到的合法数列个数（包括不再加数）。按下一步的选择分类：不再加数算 1 种；加入 j（1 \leq j \leq \lfloor i/2\rfloor）后最后一项变成 j，之后有 f_{j} 种。所以
f_{i} = 1 + \sum_{j = 1}^{\lfloor i/2\rfloor}f_{j},\quad\quad f_{1} = 1
答案为 f_{n}。f_{i} 依赖的 f_{j} 都满足 j \leq i/2 < i，i 从 2 循环到 n 即可。内层求和总计约 \frac{n^{2}}{4} = 2.5 \times 10^{5} 次加法，已经可以通过。
再用 2.2 节的方法化简。比较 f_{i} 与 f_{i - 1} 的求和上界 \lfloor i/2\rfloor 与 \lfloor(i - 1)/2\rfloor：
- i 为奇数时两者相等，f_{i} = f_{i - 1}。
- i 为偶数时前者多 1，f_{i} = f_{i - 1} + f_{i/2}。
化简后每项 O(1)，总复杂度 O(n)，代码只有两行。用 f_{2} 检验：f_{2} = f_{1} + f_{1} = 2，对应 \lbrack 2\rbrack、\lbrack 2,1\rbrack，正确。
数据类型：f_{1000} = 1981471878，小于 2^{31} - 1 = 2147483647，int 够用，但余量很小，应当先把 n = 1000 的结果算出来再决定类型。
得分要点
- 状态是「当前最后一项」，因为后续能接什么只和它有关；答案是 f_{n}。
- 「不再加数」本身算 1 种，递推式里的常数 1 不能漏。
- 化简时按 i 的奇偶分类，偶数多出的一项是 f_{i/2}。
- 化简后仍要访问 f_{i/2}，数组不能只保留相邻两项。
参考代码
#include
using namespace std;
int n;
int f[1005]; // f[i] = 以 i 开头的合法数列个数，f[1000] 约 2e9，int 刚好够
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n;
// 初始条件：1 后面不能再接数，只有 [1] 这一个
f[1] = 1;
for (int i = 2; i <= n; i++) {
// 原式 f[i] = 1 + f[1] + ... + f[i/2]
// 和 f[i-1] 相比：i 是奇数时求和范围相同，i 是偶数时多出一项 f[i/2]
f[i] = f[i - 1];
if (i % 2 == 0) f[i] += f[i / 2];
}
cout << f[n] << '\n';
return 0;
}
复杂度分析
- 时间复杂度：O(n)；未化简的递推为 O\left( n^{2} \right)。
- 空间复杂度：O(n)。
算法思考：推出带求和号的递推式后，把 f_{i} 与 f_{i - 1} 并排写出比较一次，常常能直接消掉求和号。这一步不增加代码量，却能把复杂度降一个数量级。
例 2：栈
题意简述
操作数序列为 1,2,\cdots,n，可以把序列头部的数压入栈，也可以把栈顶的数弹出到输出序列。求可能得到的输出序列总数，1 \leq n \leq 18。样例：n = 3 输出 5。
思路分析
不同的合法操作序列得到不同的输出序列，所以统计合法操作序列即可。直观写法是枚举全部 2n 次操作、每次选入栈或出栈，再检验是否合法，n = 18 时要枚举 2^{36} \approx 6.9 \times 10^{10} 种，无法完成。
按最后一步分类不容易写出式子，因为最后一次出栈之前栈里的情况很多。换一个分类依据，用 2.3 节的分段计数。设 h[i] 为 i 个数的出栈序列个数。盯住第一个进栈的数：设它是第 j + 1 个出栈的。在它出栈之前，恰好有 j 个数在它上方完成了全部进栈、出栈，方案数为 h_{j}；它出栈之后，剩下 i - 1 - j 个数独立完成，方案数为 h_{i - 1 - j}。两段互不影响，由乘法原理相乘，再对 j 求和：
h_{i} = \sum_{j = 0}^{i - 1}h_{j}\, h_{i - 1 - j},\quad\quad h_{0} = 1
h_{0} = 1 表示空序列算 1 种，j = 0 或 j = i - 1 时有一段为空，都要用到它。
这就是卡特兰数。它还有一个一阶递推式 h_{i} = \frac{h_{i - 1}\,(4i - 2)}{i + 1}，每项 O(1)。用这个式子要先乘后除，并注意中间结果：h_{17} \times 70 \approx 9.1 \times 10^{9} 已超过 int，要用 long long。本题 n \leq 18，两种写法都很快，参考代码用分段计数的式子，它说明了递推式的来历，也适用于其他分段计数问题。
另一种建式方法是设二维状态 f[x][y]，表示还有 x 个数没进栈、栈中有 y 个数时，之后能得到的输出序列数，按下一步入栈或出栈分类。这种写法更直接，但状态多一维，本题两种都能通过。
数据类型：h_{18} = 477638700，式中乘积的最大值远小于它，int 够用。
得分要点
- 分段的关键事件要选好：第一个进栈的数何时出栈，把问题切成互不影响的两段。
- h_{0} = 1 不能漏，空段的方案数为 1。
- 用一阶递推式时先乘后除，中间结果用 long long。
- 卡特兰数还可以计算 n 对括号的合法括号序列数等问题，套用结论前要核对题目与 h_{n} 的下标对应关系。
参考代码
#include
using namespace std;
int n;
int h[20]; // h[i] = i 个数的出栈序列个数，h[18] = 477638700
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n;
// 初始条件：0 个数只有“空序列”这 1 种
h[0] = 1;
for (int i = 1; i <= n; i++) {
// 看第一个进栈的数：它出栈前恰好有 j 个数进出完毕，之后还剩 i-1-j 个
for (int j = 0; j < i; j++)
h[i] += h[j] * h[i - 1 - j];
}
cout << h[n] << '\n';
return 0;
}
复杂度分析
- 时间复杂度：O\left( n^{2} \right)，n = 18 时约 171 次乘加。
- 空间复杂度：O(n)。
算法思考：按最后一步分类写不出递推式时，换一个分类依据。方案能按某个事件切成独立的两段时，用乘法原理算每一类、加法原理求总数，就得到 h_{i} = \sum h_{j}h_{i - 1 - j} 这种卷积形式的递推式。
例 3：Hanoi 双塔问题
题意简述
A 柱上有 2n 个圆盘，共 n 种尺寸，每种尺寸两个且不加区分。规则同经典汉诺塔，求把它们全部移到 C 柱的最少次数 A_{n}，1 \leq n \leq 200。样例：n = 1 输出 2，n = 2 输出 6。
思路分析
最少步数题的建式思路是分析过程中哪些步骤必不可少。考虑最大的一对盘子：它们要从 A 移到 C，至少各移动 1 次。第一次移动它们时，其余 2(n - 1) 个盘子既不能在 A 上（压在上面），也不能在 C 上（目标柱要空出来），只能全部在 B 上，把它们移过去至少要 A_{n - 1} 步；最大一对到达 C 后，还要把这 2(n - 1) 个盘子从 B 移到 C，又至少 A_{n - 1} 步。这个下界可以达到，所以
A_{n} = 2A_{n - 1} + 2,\quad\quad A_{1} = 2
这是 2.4 节的一阶线性递推，p = 2，q = 2，\frac{q}{p - 1} = 2。两边同时加 2，得到 A_{n} + 2 = 2\left( A_{n - 1} + 2 \right)，数列 \{ A_{n} + 2\} 是公比为 2 的等比数列，首项 A_{1} + 2 = 4，所以
A_{n} = 2^{n + 1} - 2
有了通项，难点就在数据范围：long long 最大约 9.2 \times 10^{18}，A_{62} = 2^{63} - 2 还能存下，A_{63} 就溢出了。50\% 的数据 n \leq 25，用 long long 可以拿到；n = 200 时 A_{200} = 2^{201} - 2 有 61 位，需要高精度。
高精度只需要实现「乘 2 加 2」：从个位开始，每一位乘 2 再加进位，把「加 2」当作个位的初始进位，一次循环完成。每位乘 2 加进位不超过 9 \times 2 + 2 = 20，进位最多为 2。
得分要点
- 两个相同尺寸的盘子不加区分，递推式是 2A_{n - 1} + 2，不是经典汉诺塔的 2h_{n - 1} + 1。
- 用 n = 1,2 检验递推式：A_{1} = 2，A_{2} = 6，与样例一致。
- long long 只能算到 n = 62，完整数据要用高精度。
- 最高位有进位时位数加 1；输出从最高位开始。
参考代码
#include
using namespace std;
int n;
int d[100]; // 大数的每一位，d[0] 是个位；答案最多 61 位
int len; // 当前位数
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n;
// 初始条件：A(1) = 2
d[0] = 2;
len = 1;
// 递推：A(i) = 2 * A(i-1) + 2，做 n-1 次
for (int i = 2; i <= n; i++) {
int jw = 2; // 把“+2”当成个位的初始进位
for (int j = 0; j < len; j++) {
int x = d[j] * 2 + jw;
d[j] = x % 10;
jw = x / 10;
}
if (jw > 0) { // 最高位有进位，位数加 1
d[len] = jw;
len++;
}
}
for (int j = len - 1; j >= 0; j--) cout << d[j];
cout << '\n';
return 0;
}
复杂度分析
- 时间复杂度：O(nL)，L \leq 61 为答案位数，约 1.2 \times 10^{4} 次单位运算。
- 空间复杂度：O(L)。
算法思考：已知模型变形时，先写出原模型的递推式，再看哪一项受影响。经典汉诺塔每次移动一个大盘，这里一次要移动一对，常数项由 1 变成 2，递推结构不变。
四、本篇小结
- 从构造过程中找状态：问「后续还能怎样做只取决于什么」，那个量就是状态（数的计算）。
- 递推式带求和号时，把相邻两项并排比较，按奇偶等情况分类，消去求和号。
- 按最后一步分类写不出式子时，找一个关键事件把方案切成独立两段，用乘法原理加加法原理建式（栈）。
- 最少步数题分析哪些步骤必不可少来建式；形如 x_{n} = p\, x_{n - 1} + q 的递推可以两边加常数化为等比数列求通项，再据此估算答案位数（Hanoi 双塔问题）。
五、系列目录与下篇预告
下一篇讲多维递推。状态从一个下标变成两个或三个下标以后，要决定「先算哪一格」：数字三角形自底向上，过河卒按行从上到下，Function 要按三个参数从小到大填一张三维表，传球游戏要先枚举传球次数。第 4 篇用这四道题讲填表顺序和多维边界的处理。
优编程，专注 C++ 信息学竞赛赛道。「递推算法」系列下一篇讲解多维递推与填表顺序，敬请关注。
——优编程信奥总教练 郑新元
