算法-递推

递推

递推思想简介

递推，意思就是用已经有的信息一点点推出想要知道的信息。

比如，平面上有一个机器人，一开始在坐标(0,0)处，第一秒向东移动一米，第二秒向南移动两米，第三秒向西移动三米，第四秒向北移动四米……机器人一直按照这个规律移动下去。由于我们知道了最开始的时候机器人的位置，我们就可以一秒一秒地推算出接下来每一个时刻机器人的位置。这就是递推。

显然，如果我们用人脑去模拟一个递推算法，是比较简单的，因为“根据已有信息推出未知信息”是我们常用的思考方式，符合直觉。

如果用电脑运行递推算法，我们应该考虑使用循环。我们可以在循环的过程中使用数组和临时变量记录下来每一步递推的过程和结果。比如在刚刚的机器人例子中，我们可以使用数组来记录每一秒结束时机器人的具体位置，使用临时变量来记录机器人当前的朝向。这和我们使用人脑模拟递推算法的区别不大。

张爽的青蛙

地上有n个石头从左到右排成一排，张爽同学养的青蛙要从第一个石头跳到最后一个石头上，每次可以选择向右跳一格或者跳两格，问总共有多少种不同的走法？ 答案对998244353取模。

比如，如果青蛙要从第一个石头跳到第五个石头，有以下五种可能的走法：

• 1->2->3->4->5
• 1->2->3->5
• 1->2->4->5
• 1->3->4->5
• 1->3->5

张爽的青蛙问题其实就是斐波那契数列的一种变形。

要使用递推解决这个问题，我们需要先对这个问题进行数学建模，找出递推式。

我们开一个数组int f[n]，其中f[i]表示从第一个石头跳到第i个石头一共有多少种方案（对998244353取模）。

接下来，我们尝试寻找递推关系：如果我们知道了f[1], f[2], f[3], ..., f[k-1]的取值，那么f[k]应该是多少呢？

$$f[k]=f[k-1]+f[k-2]$$

首先，最后一步肯定会落在k上，我们不妨把所有从1走到k的路径分成两类：一种路径是最后一步跳了一个石头，另外一种是最后一步跳了两个石头。

最后一步跳了一个石头：

• 1->2->3->4->5
• 1->2->4->5
• 1->3->4->5

最后一步跳了两个石头：

• 1->2->3->5
• 1->3->5

再抽象一点，这两类路径是：

• 先从1走到k-1，再走一步到k
• 先从1走到k-2，再一次走两个石头到k

而从1走到k-1的方案数是f[k-1]，从1走到k-2的方案数是f[k-2]，所以我们有：

• 先从1走到k-1，再走一步到k，有f[k-1]种方法
• 先从1走到k-2，再一次走两个石头到k，有f[k-2]种方法

所以从1走到k的方案数就是f[k] = f[k-1] + f[k-2]，这就是我们需要的递推式。

同时，我们知道f[1] = f[2] = 1，因为从1走到1只有一种方案（呆在原地不动），从1走到2也只有一种方案（走一格）。这便是递推的初始条件。

接下来，就是把初始条件和递推式写成循环，得到结果：

#include <bits/stdc++.h>
using namespace std;
const int MOD = 998244353; // 答案对998244353取模。
int k, f[1000010];

int main() {
    cin >> k;
    f[1] = f[2] = 1; // 初始条件
    for( int i = 3; i <= k; ++i )
        f[i] = (f[i-1] + f[i-2]) % MOD; // 递推式，记得取模
    cout << f[k] << endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

卡特兰数

让我们再来看一个有趣的问题，卡特兰数：

由n对括号组成的括号序列，有多少种是合法的括号序列？答案对998244353取模。

什么是合法的括号序列？其定义如下：

• 空序列是合法的括号序列
• 如果A是合法的括号序列，那么(A)是合法的括号序列
• 如果A和B是合法的括号序列，那么AB也是合法的括号序列

简单通俗地讲，合法的括号序列就是：任何一个左括号都必须有与之对应的右括号，任何一个右括号都必须有与之对应的左括号。

比如：

• ()(()(()))是合法的括号序列
• )(不是合法的括号序列，因为第一个右括号没有与之对应的左括号
• (()))不是合法的括号序列，因为最后一个右括号没有与之对应的左括号

类似的，如果我们想用递推解决问题，我们就要找到递推式。首先开一个数组int f[n]，用f[i]来表示i对括号能够组成多少种合法的括号序列。那么，怎么根据f[0], f[1], f[2], ..., f[k-1]的值推出f[k]的值呢？

我们继续使用分类讨论的思想：由于合法括号序列的最后一个字符一定是右括号，不妨假设最终的括号序列长成这个样子：A(B)。其中，A和B都是合法括号序列（注意A和B可以是空序列）。

我们把最终的序列分成k种：

• A由0对括号组成，B由k-1对括号组成，这样的序列有f[0] * f[k-1]种
• A由1对括号组成，B由k-2对括号组成，这样的序列有f[1] * f[k-2]种
• A由2对括号组成，B由k-3对括号组成，这样的序列有f[2] * f[k-3]种
• ……
• A由m对括号组成，B由k-1-m对括号组成，这样的序列有f[m] * f[k-1-m]种
• ……
• A由k-1对括号组成，B由0对括号组成，这样的序列有f[k-1] * f[0]种

于是我们就得到了递推式：

$$f(n)=\sum _{k=0}^{n-1}f(k)\times f(n-k-1)$$

同样，初始条件是f[0] = 1，因为0对括号只能组成一种括号序列（空序列）。

至此，代码呼之欲出：

#include <bits/stdc++.h>
using namespace std;
const int MOD = 998244353;
int n, f[100010];

int main() {
    cin >> n;
    f[0] = 1; // 初始条件
    for( int i = 1; i <= n; ++i ) { // 求f[i]的值
        for( int k = 0; k < i; ++k ) {
            f[i] += int((long long)f[k] * f[i-k-1] % MOD); // 递推式
            // 注意，两个int相乘的结果可能爆int，因此乘法的过程要转换成long long以避免整数溢出
            f[i] %= MOD; // 记得取模
        }
    }
    cout << f[n] << endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

容易发现，该算法核心递推式的执行次数是：1 + 2 + 3 + ... + n，因此算法复杂度是O(n^2)。

总结

• 递推思想：

  根据已有的东西一点点地推出未知的东西。

• 使用递推解题三步骤：

  • 数学建模
  • 找出递推式和初始条件
  • 写出代码。

• 张爽的青蛙（斐波那契）问题：地上有n个石头从左到右排成一排，张爽同学养的青蛙要从第一个石头跳到最后一个石头上，每次可以选择向右跳一格或者跳两格，问总共有多少种不同的走法？

  • 递推式：f[n] = f[n-1] + f[n-2]；
  • 初始条件：f[1] = f[2] = 1。因为从1走到1只有一种方案（呆在原地不动），从1走到2也只有一种方案（走一格）；
  • 完整代码：

#include <bits/stdc++.h>
using namespace std;
const int MOD = 998244353; // 答案对998244353取模。
int k, f[1000010];

int main() {
    cin >> k;
    f[1] = f[2] = 1; // 初始条件
    for( int i = 3; i <= k; ++i )
        f[i] = (f[i-1] + f[i-2]) % MOD; // 递推式，记得取模
    cout << f[k] << endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

• 卡特兰数问题：由n对括号组成的括号序列，有多少种是合法的括号序列？
  • 递推式：f[n] = f[0] * f[k-1] + ... + f[k-1] * f[0]；
  • 初始条件：f[0] = 1，因为0对括号只能组成一种括号序列（空序列）；
  • 完整代码：

#include <bits/stdc++.h>
using namespace std;
const int MOD = 998244353;
int n, f[100010];

int main() {
    cin >> n;
    f[0] = 1; // 初始条件
    for( int i = 1; i <= n; ++i ) { // 求f[i]的值
        for( int k = 0; k < i; ++k ) {
            f[i] += int((long long)f[k] * f[i-k-1] % MOD); // 递推式
            // 注意，两个int相乘的结果可能爆int，因此乘法的过程要转换成long long以避免整数溢出
            f[i] %= MOD; // 记得取模
        }
    }
    cout << f[n] << endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

• 时间复杂度：O(n^2)。

贴瓷砖

有一块大小是 2*n 的墙面，现在需要用2种规格的瓷砖铺满，瓷砖规格分别是 2 * 1 和 2 * 2，请计算一共有多少种铺设的方法。

输入描述：

输入的第一行包含一个正整数T（T<=20），表示一共有T组数据，接着是T行数据，每行包含一个正整数N（N<=30），表示墙面的大小是2行N列。

输出描述：

输出一共有多少种铺设的方法，每组数据的输出占一行。

示例 1：

输入：

2
8
12
1
2
3

输出：

3
171
2731
1
2
3

2行2列会有两种贴法，2行1列有一种贴法

因此关系是f[i] = f[i-1] + f[i-2]*2

递推思想的应用

错位排列

我们尝试使用递推算法来解决更实际且更难的问题，在这个过程中，我们会用到更多的数学建模和逻辑推理。

错位排列

有n个信封和n个信件，第i个信件属于第i个信封，我们想知道，有多少种不同的方法，使得没有任何一个信件被装入正确的信封中？答案对998244353取模。

下图中，2号信件装入了2号信封中，因此方案不合法：

而下图，就满足“任何一个信件都没有被装入正确的信封中”，因此是合法方案：

我们开一个数组int f[n];，其中f[i]表示当信封和信件数量为i的时候，总方案数是多少。

$$f[n]=(n-1)(f[n-1]+f[n-2])$$

错位排列建模

回顾我们之前讲的使用递推解题三步骤：

• 数学建模
• 找出递推式和初始条件
• 写出代码。

我们继续尝试使用分类讨论的方法寻找递推式。

错位排列

有n个信封和n个信件，第i个信件属于第i个信封，我们想知道，有多少种不同的方法，使得没有任何一个信件被装入正确的信封中？答案对998244353取模。

考虑1号信件，它不能被装入1号信封，不妨假设它被装入了x号信封。这里为了方便，我们假设x = 3。

那么x号信件可以装入哪个信封呢？这里又存在两种情况。

第一种情况：x号信件装入了1号信封：

在这种情况下，我们可以去掉1号和x号，就变成了完全独立的子问题：n-2个信件和信封的错位排列问题。

第二种情况：x号信件没有装入1号信封。

这个时候，如果我们去掉1号信件和x号信封，情况就会变成下图：

2号、4号、5号信件不能装入对应的信封中，而x号信件不能装入1号信封中，这其实也是一个大小为n-1的错位排列问题。

因此，当1号信件装入x号信封的时候，总共会有两种情况：

• x号信件装入1号信封，有f[n-2]种方案
• x号信件不装入1号信封，有f[n-1]种方案

而x的选择有n-1种（除了1都可以），因此我们得到了递推式f[n] = (n-1)(f[n-1] + f[n-2])。

同时，我们也可以轻易得到两个边界条件：

• f[1] = 0，因为只有1个信件和信封的时候，没有办法错位排列。
• f[2] = 1，只有2个信件和信封的时候，只有一种方法（交叉放）。

#include <bits/stdc++.h>
using namespace std;
const int MOD = 998244353;

int n = 10;
int f[1000010];
    
int main() {
    f[1] = 0; // 初始条件
    f[2] = 1;
    for( int i = 3; i <= n; ++i ) {
        // TODO 请补全下述代码
        f[i] = int((long long)(f[i-1] + f[i-2]) * (i-1) % MOD);  // 请补全递推式，记得取模
        // 注意，两个int相乘的结果可能爆int，因此乘法的过程要转换成long long以避免整数溢出
    }
    cout << f[n] << endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

杨辉三角（二维递推）

事实上，我们也会经常遇到不止一维的递推，比如我们接下来要介绍的杨辉三角问题。

从n个不同的物品中选取m个，有多少种不同的选择方法？这是一个经典的组合数问题，而本题需要你解决一个更难的问题：给出k，你需要输出一个$(k+1)\ast (k+1)$的矩阵，其中第i行第j列表示，从i个不同的物品中选j个，有多少种不同的方法（行和列的标号从0开始）。所有答案对998244353取模。

比如，当k=4时，你需要输出如下矩阵：

1 0 0 0 0
1 1 0 0 0
1 2 1 0 0
1 3 3 1 0
1 4 6 4 1
1
2
3
4
5

其中第4行第2列的数字为6（注意行和列从0开始标号），表示从4个不同的物品中选2个有6种方法。

假设这4个物品分别叫A、B、C、D，那么这6种方法分别是：

AB
AC
AD
BC
BD
CD
1
2
3
4
5
6

类似的，我们开一个二维数组int f[k][k];，其中f[i][j]表示从i个物品中选j个的方案数，接下来，我们要做的就是寻找递推式。

怎么尝试寻找递推式呢？分类讨论吗？对的！我们继续使用分类讨论来寻找递推式。绝大多数简单的递推问题都可以用分类讨论的方法找到一个合理的递推式。

假设我们现在要求的值是f[i][j]，即，从i个物品中选j个的方案数，我们不妨把i个物品从1到i标上号。

现在考虑1号物品，我们尝试对1号物品进行分类讨论。怎么分类呢？无非就是两类：选1号物品，还是不选1号物品。

• 选1号物品：由于1号物品是一定要选进来的，因此我们还剩i-1个物品，我们要从中选出j-1个物品，方案数是f[i-1][j-1]。
• 不选1号物品：我们还剩i-1个物品，但是1号一定不选，因此我们还要从剩下的i-1个物品中选出j个物品，方案数是f[i-1][j]。

结束了吗？其实这样就结束了。因为我们已经不重复不遗漏地考虑到了所有可能出现的情况。

所以我们就得到了**递推式*f[i][j] = f[i-1][j-1] + f[i-1][j]。

别忘了，我们还要考虑递推的边界条件！二维递推的边界条件比一维递推要复杂得多。

首先观察样例矩阵，我们可以轻易发现，所有j > i的位置都是0，因为我们不可能从i个物品中选出大于i个物品，因此这些位置一定是0。

接下来，我们发现样例矩阵的第一列和对角线全都是1，这也是容易推理出的：第一列的所有元素都是f[x][0]，从x个物品中选取0个物品，显然只有一种方案：什么都不选；而对角线的所有元素都是f[x][x]，从x个物品中选出x个物品，也只有一种方案：全部都选上。

除此之外还有其他的边界条件吗？

没有了。

因为我们的递推式f[i][j] = f[i-1][j-1] + f[i-1][j]告诉我们，如果我们想要计算任何一个数字f[i][j]，只需要知道它“上面”的数字f[i-1][j]和“左上方”的数字f[i-1][j-1]即可。观察矩阵，我们发现，对于任何一个数字，我们都可以用已知的初始条件推出，因此我们不需要更多的边界条件了。

除此之外还有什么需要注意的么？有的！我们还需要特别注意递推的顺序！二维递推不同于一维递推，二维的数据可能存在莫名其妙的依赖关系，因此我们在写二维递推的时候，需要特别注意二维递推的顺序。

比如杨辉三角，我们可以从递推式和上图看出，f[i]这一行的值全部由f[i-1]这一行的值推出，因此我们只需要按照行数从小到大的顺序递推即可。而其他形式的二维递推可能就需要用其他顺序进行循环，比如下面这种递推形式。

搞定了递推式、初始条件、递推顺序之后，我们的代码就呼之欲出了。

同时，递推出单个元素的复杂度是O(1)，整个表格一共有O(n^2)个元素，因此该算法的总时间复杂度是O(n^2)。

#include <bits/stdc++.h>
using namespace std;
const int MOD = 998244353;

int k = 10;
int f[2010][2010] = {0}; // 初始化f数组为全0

    
int main() {
    for( int i = 0; i <= k; ++i ) {
        f[i][0] = f[i][i] = 1; // 递推边界条件
        for( int j = 1; j < i; ++j ) {
            // TODO 请补全下述代码
            f[i][j] = f[i-1][j-1] + f[i-1][j]; // 请补全递推式，记得取模
        }
        for( int j = 0; j <= k; ++j ) {
            cout << f[i][j] << ' '; // 输出这一整行
        }
        cout << endl;
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

总结

• 递推思想：

  根据已有的东西一点点地推出未知的东西。

• 使用递推解题三步骤：

  • 数学建模
  • 找出递推式和初始条件
  • 写出代码。

• 错位排列问题：有n个信封和n个信件，第i个信件属于第i个信封，我们想知道，有多少种不同的方法，使得没有任何一个信件被装入正确的信封中？

  • 递推式：f[n] = (n-1)(f[n-1] + f[n-2])；
  • 初始条件：f[1] = 0，因为只有1个信件和信封的时候，没有办法错位排列；f[2] = 1，只有2个信件和信封的时候，只有一种方法（交叉放）。
  • 完整代码：

#include <bits/stdc++.h>
using namespace std;
const int MOD = 998244353;

int f[1000010], n;

int main() {
    cin >> n;
    f[1] = 0; // 初始条件
    f[2] = 1;
    for( int i = 3; i <= n; ++i ) {
        f[i] = (long long)(i-1) * (f[i-1] + f[i-2]) % MOD;
        // 注意取模，并且小心乘法会爆int
    }
    cout << f[n] << endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

• 杨辉三角（二维递推）问题：从n个不同的物品中选取m个，有多少种不同的选择方法？这是一个经典的组合数问题，而本题需要你解决一个更难的问题：给出k，你需要输出一个(k+1)∗(k+1)的矩阵，其中第i行第j列表示，从i个不同的物品中选j个，有多少种不同的方法（行和列的标号从0开始）。
  • 递推式：f[i][j] = f[i-1][j-1] + f[i-1][j]；
  • 初始条件：f[i][0] = f[i][i] = 1; // 递推边界条件；
  • 完整代码：

#include <bits/stdc++.h>
using namespace std;
const int MOD = 998244353;

int f[2010][2010] = {0}, k; // 初始化f数组为全0

int main() {
    cin >> k;
    for( int i = 0; i <= k; ++i ) {
        f[i][0] = f[i][i] = 1; // 递推边界条件
        for( int j = 1; j < i; ++j ) {
            f[i][j] = (f[i-1][j-1] + f[i-1][j]) % MOD; // 递推式，记得取模
        }
        for( int j = 0; j <= k; ++j ) {
            cout << f[i][j] << ' '; // 输出这一整行
        }
        cout << endl;
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

• 时间复杂度：O(n^2)。