Note - 递推与递归

2021/11/16:修了一下以前的 markdown

递推

定义

递推算法是一种用若干步可重复运算来描述复杂问题的方法。递推是序列计算中的一种常用算法。通常是通过计算前面的一些项来得出序列中的指定项的值。

第一类： 斐波那契数列

有很多递推的基础题都是以斐波那契数列为基础的，例如我们的铺砖系列：
铺砖1
递推式就是我们原始的斐波那契数列：

边界条件：\(a_1 = 1, a_2 = 1\)
递推式：\(a_i = a_{i-1} + a_{i-2}\)

其他的类似题也不过是以此递推式变形罢了

第二类： Hanoi塔

其实跟上面也差不多

边界条件：\(a_1 = 1\)
递推式：\(a_i = a_{i-1}×2+1\)

第三类：平面分割问题

平面分割1
这道题目其实看图都能看出规律来
2，4，8，14.......
\(code\)

#include 
using namespace std;
int main() {
    int n;
    cin >> n;
    int a[46346] = {};
    a[1] = 2;
    int tot = 0;
    for (int i = 2; i <= n; i++) {
        tot += 2;
        a[i] = a[i - 1] + tot;
    }
    cout << a[n];
    return 0;
}

第四类： Catalan

终于到我们的 \(Catalan\) 了，这是考试最常考的一类，很多题目都以此为模板，进行递推。比如树屋阶梯。。。
我们就以经典题目凸n边形的不同划分方式为例。

我们设凸 \(n\) 边形的不同划分方式有 \(a_n\) 种。给凸 \(n\) 边形的每一个角都编上号，从 \(1\) 到 \(n\) 。现在固定住 \(1\) 和 \(n\) 角，在其它顶点上任意选一个顶点 \(j\)，连接 \(1\) 、 \(j\) 和 \(n\) 、 \(j\) ，发现把这个凸n边形分成了三个形状，第一个是一个 \(j\) 边形，第二个是一个三角形，第三个是一个 \(n - j + 1\) 边形。我们知道 \(j\) 边形有 \(a_j\) 种不同划分方式， \(n - j + 1\) 边形有 \(a_{n - j + 1}\) 种不同划分方式，所以通过乘法原理，所以 \(i\) 边形就有 \(a_{i - j + 1} × a_j\) 种划分方式。

边界条件：
\(a[1] = a[2] = 1\)

递推式：
\(a[i] = \displaystyle\sum_{j = 1}^{n - 2} a[i-j+1]×a[j]\)

第五类：第二类stirling数

例题：合理放球
这是一道典型的二维递推

我们可以设 \(a_{i,j}\) 表示 \(i\) 个球放入 \(j\) 个箱子里面
我们发现；
当 \(i < j\) 或者 没有箱子的时候肯定就没法放，所以 \(a_{i,j} = 0\);
当 \(i == j\) 时，当且仅当只有一种方案，故 \(a_{i,j} = 1\)
当 只有一个箱子是肯定只有一种，故 \(a_{i,j} = 1\)
当 只有一个球时，前面已经判断过不止一个箱子所以不管怎么弄也只有 \(0\) 种方案
如果上述条件都不满足，就
\(a_{i,j} = a_{i-1,j-1} + j × _{i-1,j}\)

\(code\)

#include 
using namespace std;
int main() {
    int n, m;
    cin >> n >> m;
    long long dp[25][25] = {};
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= m; j++) {
            if (i < j || j == 0)
                dp[i][j] = 0;
            else if (i == j)
                dp[i][j] = 1;
            else if (j == 1)
                dp[i][j] = 1;
            else if (i == 1)
                dp[i][j] = 0;
            else
                dp[i][j] = dp[i - 1][j - 1] + j * dp[i - 1][j];
        }
    }
    cout << dp[n][m];
    return 0;
}

好了，递推部分就结束了，下面我们就将迎来我们的递归算法

递归

递归是啥，能吃吗？
递归就是在函数体内部调用自己本身的一种算法（非官方定义）
我们就拿上文提到的斐波那契数列举例吧！
先给出代码：

#include 
int f(int n) {
	if (n == 1) return 1;
	else if (n == 2) return 2;
	else return f(n - 1) + f(n - 2);
}
int main() {
	int n;
	scanf("%d", &n);
	printf("%d", f(n));
	return 0;
}

递归最重要的部分叫做递归出口。例如，以上代码的递推出口就是

if (n == 1) return 1;
else if (n == 2) return 2;

如果一个递归没有递归出口的话，那会是相当恐怖的。。。有兴趣的同学可以运行一下以下代码：

#include 
#include 
int f(int n) {
	system("start https://blog.csdn.net/weixin_51306163");
	f(n + 1);
}
int main() {
	f(1);
	return 0;
}

明白了递归的基本用法过后，下面我们就来用递归来实现 \(n\) 的全排列。
(什么\(?\)全排列还要用手打，不是有 \(next\_permutation\) 吗\(?\))
这算得上一道简单的回溯了。

思路：
\(1.\) 用一个 \(b\) 数组保存已经用过的第 \(i\) 号位
\(2.\) 用一个 \(a\) 数组保存答案
\(3.\) 在函数里遍历 \(0 -strlen(st)\) 如果发现第 \(i\) 号位没有被用过，就将这一位保存在答案数组里。并判断找到的 \(t\) 是否等于 \(strlen(st)\) 如果相等则输出解，否则继续搜索并回溯。

\(code\)

#include 
using namespace std;
int n;
char a[15], st[15];
bool b[15] = {};
int print();
int search(int t) {
    for (int i = 0; i <= n; i++) {
        if (!b[i]) {
            a[t] = st[i];
            b[i] = true;
            if (t == n + 1) {
                print();
            } else
                search(t + 1);
            b[i] = false;
        }
    }
}
int print() {
    for (int i = 1; i <= n + 1; i++) {
        printf("%c", a[i]);
    }
    printf("\n");
}
int main() {
    gets(st);
    n = strlen(st);
    search(1);
    return 0;
}

什么？？？刚刚写的斐波那契数列超时了！！！
我们可以输出 \(n\) 看一下

我们发现，\(n\) 重复计算了很多次，这样就很容易超时。所以我们可以用一个数组来保存 \(f(n)\) 的值，这样避免了很多重复计算。
就像这样:

#include 
int data[55];
int f(int n) {
	if (data[n] != 0) return data[n];
	else {
		if (n == 1) data[n] = 1;
		else if (n == 2) data[n] = 2;
		else return data[n] = f(n - 1) + f(n - 2);
		return data[n];
	}
}
int main() {
	int n;
	scanf("%d", &n);
	printf("%d", f(n));
	return 0;
}

这就是记忆化递归，在搜索 的时候会起到很大作用。

若有错误的地方， 请各位大佬指出