递归与递推

递归

• 直白理解：函数在其内部调用自身（自己调用自己）
• 所有递归都可以采用递归搜索树来理解
• 递归的特点：
  • 一般来说代码较为简短，但是理解难度大
  • 一般时间和空间消耗较大，容易产生重复计算，可能爆栈

递归实现指数型枚举

题目描述

从 1∼n 这 n 个整数中随机选取任意多个，输出所有可能的选择方案。

输入格式

输入一个整数 n。

输出格式

每行输出一种方案。

同一行内的数必须升序排列，相邻两个数用恰好 1 个空格隔开。

对于没有选任何数的方案，输出空行。

本题有自定义校验器（SPJ），各行（不同方案）之间的顺序任意。

数据范围

1 <= n <= 15

输入样例

3

输出样例

32
2 3
1
1 3
1 2
1 2 3

思路：递归（DFS）

• 从1 ~ n依次参考每一个数，选或者不选。

• 举个栗子：

  当n = 2时

  

从1~n依次考虑这个数选或者不选。

AC代码

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>using namespace std;const int N = 16;int n;
int nums[N]; //记录当前位置的状态，0：还没考虑，1：选它，2：不选它 void dfs(int curr) {if (curr > n) {for (int i = 1; i <= n; i++) { //if (nums[i] == 1) {cout << i << " ";}}cout << endl;return;}nums[curr] = 2; //当前位置不选dfs(curr + 1); // 第一个分支：不选当前位置nums[curr] = 0; // 恢复现场，此处该语句可省略nums[curr] = 1; //当前位置选dfs(curr + 1); // 第二个分支：选当前位置nums[curr] = 0; // 恢复现场，此处该语句可省略
}int main()
{cin >> n;dfs(1); //传入当前枚举的位置，从第一位开始枚举return 0;
}

变式：将所有方案记录下来

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>using namespace std;const int N = 16;int n;
int nums[N]; //记录当前位置的状态，0：还没考虑，1：选它，2：不选它
vector<vector<int> > ways; //用来记录每一个方案void dfs(int curr) {if (curr > n) {vector<int> way;for (int i = 1; i <= n; i++) { //记录方案if (nums[i] == 1) {way.push_back(i);}}ways.push_back(way);return;}nums[curr] = 2; //当前位置不选dfs(curr + 1); // 第一个分支：不选当前位置nums[curr] = 0; // 恢复现场，此处该语句可省略nums[curr] = 1; //当前位置选dfs(curr + 1); // 第二个分支：选当前位置nums[curr] = 0; // 恢复现场，此处该语句可省略
}int main()
{scanf("%d", &n);dfs(1); //传入当前枚举的位置，从第一位开始枚举for (int i = 0; i < ways.size(); i++) {for (int j = 0; j < ways[i].size(); j++) {printf("%d ", ways[i][j]);}puts("");}return 0;
}

递归实现排列型枚举

题目描述

把 1∼n 这 n 个整数排成一行后随机打乱顺序，输出所有可能的次序。

输入格式

一个整数 n。

输出格式

按照从小到大的顺序输出所有方案，每行 1 个。

首先，同一行相邻两个数用一个空格隔开。

其次，对于两个不同的行，对应下标的数一一比较，字典序较小的排在前面。

数据范围

1 <= n <= 9

输入样例

3

输出样例

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

思路：递归（DFS）

全排列问题有两种理解思路：

• 顺序一：依次枚举每个数放到哪个位置

• 顺序二：依次枚举每个位置放哪个数

  以顺序二为例：

  当n = 3时：

AC代码

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>using namespace std;const int N = 10;int n;
int state[N]; //记录当前方案；0表示还没放数； 1~n表示放入的数字
bool used[N]; //记录当前的数是否被使用；true：使用过； false：还未使用void dfs(int curr) {if (curr > n) { //判断边界for (int i = 1; i <= n; i++) { //输出方案printf("%d ", state[i]);}puts("");return;}//一次枚举每个分支，即当前位置可以填哪些数for (int i = 1; i <= n; i++) { //按字典序从小到大一次枚举if (!used[i]) {state[curr] = i; //填入该数used[i] = true; //记录该数已被选用dfs(curr + 1); //枚举下一个位置//恢复现场state[curr] = 0; //该语句此处可以省略used[i] = false;}}
}int main()
{cin >> n;dfs(1); //传入当前枚举的位置，从第一位开始枚举return 0;
}

递归实现组合型枚举

题目描述

把 1∼n 这 n 个整数中随机选出 m 个，输出所有可能的选择方案。

输入格式

两个整数 n，m在同一行用空格隔开。

输出格式

按照从小到大的顺序输出所有方案，每行 1 个。

首先，同一行内的数升序排列，相邻两个数用一个空格隔开。

其次，对于两个不同的行，对应下标的数一一比较，字典序较小的排在前面（例如 1 3 5 7 排在 1 3 6 8 前面）

数据范围

n > 0,

0 <= m <= n,

n + (n - m) <= 25

输入样例

5 3

输出样例

1 2 3 
1 2 4 
1 2 5 
1 3 4 
1 3 5 
1 4 5 
2 3 4 
2 3 5 
2 4 5 
3 4 5 

思路：递归（DFS）

• 题目要求是组合型枚举
• 不能含重复项
• 每一组数据从小到大排列

当n = 5，m = 3时，仅有以下几种符合要求：（其余分支无法凑满3个数，因此舍弃）

在枚举每个位置的时候，将数字从小到大枚举（这里考虑局部属性，只需保证新加的数大于前一个数）

考虑需要的参数：（全局变量、形参）

• 参数一：m个位置，用来存入数据。way[N]
• 参数二：当前枚举到哪个位置。curr
• 参数三：当前最小可以从哪个数开始枚举。start

AC代码

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>using namespace std;const int N = 30;int n, m;
int way[N]; //用来记录当前方案。0表示还未放入数据；1~n表示存入的数据void dfs(int curr, int start) {if (curr == m + 1) { //边界判断，已经选了m个数for (int i = 1; i <= m; i++) { //输出方案printf("%d ", way[i]);}puts("");return;}for (int i = start; i <= n; i++) { //每次从start开始枚举，保证后一个数比前一个数大way[curr] = i; //将数据i放入当前位置dfs(curr + 1, i + 1);way[curr] = 0; //回复现场，此处可以省略}
}int main()
{scanf("%d%d", &n, &m);dfs(1,1); //第一个参数：从第一个位置开始枚举。第二个参数：最小可以从1开始枚举return 0;
}

剪枝优化

• 当枚举到第curr个位置时，表示正在选第curr个数，此时已经选好了curr - 1个数
• 剩下可供选择的数为从start到n，共有n - start + 1
• 当选中的数和剩下的所有数加起来不够m个数时，表示此方案无解，可以提前舍弃。
• curr - 1 + n - start + 1 < m**（即curr + n - start < m）**

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>using namespace std;const int N = 30;int n, m;
int way[N]; //用来记录当前方案。0表示还未放入数据；1~n表示存入的数据void dfs(int curr, int start) {//剪枝，当后面的所有数加起来不够m个时，直接返回if (curr + n - start < m) {return;}if (curr == m + 1) { //边界判断，已经选了m个数for (int i = 1; i <= m; i++) {printf("%d ", way[i]);}puts("");return;}for (int i = start; i <= n; i++) { //每次从start开始枚举，保证后一个数比前一个数大way[curr] = i; //将数据i放入当前位置dfs(curr + 1, i + 1);way[curr] = 0; //回复现场，此处可以省略}
}int main()
{scanf("%d%d", &n, &m);dfs(1,1); //第一个参数：从第一个位置开始枚举。第二个参数：最小可以从1开始枚举return 0;
}

带分数

题目描述

100 可以表示为带分数的形式：100 = 3 + $\frac{69258}{714}$

还可以表示为：100 = 82 + $\frac{3546}{197}$

注意特征：带分数中，数字 1∼9
分别出现且只出现一次（不包含 0）。

类似这样的带分数，100有11种表示法。

输入格式

一个正整数n。

输出格式

输出输入数字用数码 1∼9 不重复不遗漏地组成带分数表示的全部种数。

数据范围

1 <= N < $10^6$

输入样例1:

100

输出样例1：

11

输入样例2:

105

输出样例2：

6

思路：递归（DFS）

上述等式可以表示为这种形式：n = a + $\frac{b}{c}$，采取一下方案来解决问题：

1. 枚举a、b、c的全排列
2. 分别枚举a、b、c的位数
3. 判断等式是否成立

• 结合题目优化一下：
  1. 将上述等式转变为：c * n = c * a + b
  2. n已知，分别枚举a和c的全排列，然后计算b是否满足要求即可。

AC代码

#include<bits/stdc++.h>
using namespace std;const int N = 20;
int n, ans; //ans用来记录最终的种数
bool st[N], backup[N]; // st数组记录当前数字是否被使用过。ture：表示使用过；false：表示未使用;backup数组用来备份stbool check(int a, int c) {long long b = n * (long long)c - a * c;if (!a || !b || !c) return false; //a,b,c均不能为0memcpy(backup, st, sizeof st); //备份st数组while (b) {int x = b % 10; //取个位数b /= 10; //删除个位数if (!x || backup[x]) return false; //依次判断b的每一个数是否被使用过backup[x] = true; //标记这个数被用过}for (int i = 1; i <= 9; i++) { //判断9个数是否都被使用过if (!backup[i])	return false;}return true;
}void dfs_c(int used, int a, int c) { // 第一个参数表示：当前已经用了多少个数字；第二个参数表示a的值；第三个参数表示c的值if (used >= n) return; //如果已经用完了n个数字，则返回if(check(a,c)) ans++; //检验a和c是否满足要求for (int i = 1; i <= 9; i++) {if (!st[i]) {st[i] = true;dfs_c(used + 1, a, c * 10 + i);st[i] = false; //恢复现场}}
}void dfs_a(int used, int a) { //第一个参数表示：当前已经用了多少个数字；第二个参数表示a的值if (a >= n) return; //如果a >= n则无解，直接返回if (a) dfs_c(used, a, 0);for (int i = 1; i <= 9; i++) {if (!st[i]) {st[i] = true;dfs_a(used + 1, a * 10 + i);st[i] = false; //恢复现场}}
}int main() {cin >> n;dfs_a(0, 0); //第一个参数表示：当前已经用了多少个数字；第二个参数表示a的值cout << ans;return 0;
}

剪枝优化

• 在枚举a的位数的时候，已经使用的数最多达到7，因为b和c至少各占一位
• 在枚举c的时候，已经使用的数最多达到8，因为b至少占一位

#include<bits/stdc++.h>
using namespace std;const int N = 20;
int n, ans; //ans用来记录最终的种数
bool st[N], backup[N]; // st数组记录当前数字是否被使用过。ture：表示使用过；false：表示未使用;backup数组用来备份stbool check(int a, int c) {long long b = n * (long long)c - a * c;if (!a || !b || !c) return false; //a,b,c均不能为0memcpy(backup, st, sizeof st); //备份st数组while (b) {int x = b % 10; //取个位数b /= 10; //删除个位数if (!x || backup[x]) return false; //依次判断b的每一个数是否被使用过backup[x] = true; //标记这个数被用过}for (int i = 1; i <= 9; i++) { //判断9个数是否都被使用过if (!backup[i])	return false;}return true;
}void dfs_c(int used, int a, int c) { // 第一个参数表示：当前已经用了多少个数字；第二个参数表示a的值；第三个参数表示c的值if (used >= 8) return; //剪枝优化，当used = 8时就可以返回了，因为b至少占一位if(check(a,c)) ans++; //检验a和c是否满足要求for (int i = 1; i <= 9; i++) {if (!st[i]) {st[i] = true;dfs_c(used + 1, a, c * 10 + i);st[i] = false; //恢复现场}}
}void dfs_a(int used, int a) { //第一个参数表示：当前已经用了多少个数字；第二个参数表示a的值if (a >= n) return; //如果a >= n则无解，直接返回if (used >= 7) return; //剪枝优化，当used = 7时就可以返回了，因为b和c至少各占一位if (a) dfs_c(used, a, 0); //当a不等于0的时候再去枚举c的可能情况for (int i = 1; i <= 9; i++) {if (!st[i]) {st[i] = true;dfs_a(used + 1, a * 10 + i);st[i] = false; //恢复现场}}
}int main() {cin >> n;dfs_a(0, 0); //第一个参数表示：当前已经用了多少个数字；第二个参数表示a的值cout << ans;return 0;
}

递推

简单斐波那契

题目描述

以下数列0 1 1 2 3 5 8 13 21 … 被称为斐波纳契数列。

这个数列从第 3 项开始，每一项都等于前两项之和。

输入一个整数 N，请你输出这个序列的前 N 项。

输入格式

一个整数 N。

输出格式

在一行中输出斐波那契数列的前 N 项，数字之间用空格隔开。

数据范围

0 < N < 46

输入样例:

5

输出样例：

0 1 1 2 3

思路：递推

• 根据数列的规律可知，数列的每一项等于其前面两项之和
• 即：f(n) = f(n - 1) + f(n - 2); (n >= 3)

AC代码

#include<bits/stdc++.h>
using namespace std;int main()
{int n, a = 0, b = 1, t;cin >> n;for (int i = 1; i <= n; i++) {cout << a << " ";t = a + b;a = b;b = t;}return 0;
}

费解的开关

题目描述

你玩过“拉灯”游戏吗？

25 盏灯排成一个 5×5 的方形。

每一个灯都有一个开关，游戏者可以改变它的状态。

每一步，游戏者可以改变某一个灯的状态。

游戏者改变一个灯的状态会产生连锁反应：和这个灯上下左右相邻的灯也要相应地改变其状态。

我们用数字 1 表示一盏开着的灯，用数字 0 表示关着的灯。

下面这种状态

10111
01101
10111
10000
11011

在改变了最左上角的灯的状态后将变成：

01111
11001
11001
10100
11011

给定一些游戏的初始状态，编写程序判断游戏者是否可能在 6 步以内使所有的灯都变亮。

输入格式

第一行输入正整数 n，代表数据中共有 n 个待解决的游戏初始状态。

以下若干行数据分为 n 组，每组数据有 5 行，每行 5 个字符。

每组数据描述了一个游戏的初始状态。

各组数据间用一个空行分隔。

输出格式

一共输出 n 行数据，每行有一个小于等于 6 的整数，它表示对于输入数据中对应的游戏状态最少需要几步才能使所有灯变亮。

对于某一个游戏初始状态，若 6 步以内无法使所有灯变亮，则输出 −1。

数据范围

0 < N <= 500

输入样例:

3
00111
01011
10001
11010
1110011101
11101
11110
11111
1111101111
11111
11111
11111
11111

输出样例：

3
2
-1

思路：递推

结合题目分析可以得出以下性质：

• 按开关的顺序是随意的，没有影响
• 每个开关最多只按一次（要求最小的触发次数，按两次等于没按）

结论：

• 每一行开关的操作，完全由上一行灯的明灭状态所决定。（能影响第一行灯状态的只有第二行灯，以此类推）
• 每操作一行只能保证当前行的前面所有行的灯都亮着，当前行无法保证。
• 因此只需要枚举第一行的所有操作即可。共2⁵ = 25种方案（利用二进制枚举）

AC代码

#include<bits/stdc++.h>
using namespace std;const int N = 6;
char nums[N][N], backup[N][N];
int dx[5] = {-1, 0, 1, 0, 0}, dy[5] = {0, 1, 0, -1, 0};void turn(int x, int y) { //改变上下左右和当前的灯for (int i = 0; i < 5; i++) {int a = x + dx[i], b = y + dy[i];if (a < 0 || a >= 5 || b < 0 || b >= 5) {continue; //越界了}nums[a][b] ^= 1; //字符'0'变'1'，'1'变'0'}
}int main()
{int n;scanf("%d", &n);while (n--) {for (int i = 0; i < 5; i++) {scanf("%s", nums[i]);}int ans = 10;for (int i = 0; i < 32; i++) {memcpy(backup, nums, sizeof nums); //将nums数组备份int step = 0;for (int t = 0; t < 5; t++) {if (i >> t & 1) {step++;turn(0, t); //改变上下左右和当前的灯}}for (int x = 0; x < 4; x++) { //检查前4行灯for (int y = 0; y < 5; y++) {if (nums[x][y] == '0')  { //如果当前位置的灯是灭的，则要按当前位置等的下一行灯的按钮step++;turn(x + 1, y); //改变上下左右和当前的灯}}}bool flag = false;for (int i = 0; i < 5; i++) { //检查最后一排灯是否都变亮if (nums[4][i] == '0') {flag = true;break;}}if (!flag) { //更新答案ans = min(ans, step);}memcpy(nums, backup, sizeof nums); //恢复nums数组}if (ans > 6) ans = -1;printf("%d\n", ans);}return 0;
}

翻硬币

题目描述

小明正在玩一个“翻硬币”的游戏。

桌上放着排成一排的若干硬币。我们用 * 表示正面，用 o 表示反面（是小写字母，不是零）。

比如，可能情形是：**oo***oooo

如果同时翻转左边的两个硬币，则变为：oooo***oooo

现在小明的问题是：如果已知了初始状态和要达到的目标状态，每次只能同时翻转相邻的两个硬币,那么对特定的局面，最少要翻动多少次呢？

我们约定：把翻动相邻的两个硬币叫做一步操作。

输入格式

两行等长的字符串，分别表示初始状态和要达到的目标状态。

输出格式

一个整数，表示最小操作步数

数据范围

输入字符串的长度均不超过100。
数据保证答案一定有解。

输入样例1:

**********
o****o****

输出样例1：

5

输入样例2:

*o**o***o***
*o***o**o***

输出样例2：

1

思路：

我们可以依据输入输出样例来进行模拟分析，可以发现以下性质：

• 一次能改变一组相邻的两枚硬币，翻两次相当于没有改变。
• 对于同一个位置，如果初始态和目标太的硬币正反不一致，则含有该硬币的一组相邻硬币一定要进行翻转。
• 题目保证样例必有解，我们可以从左到右进行模拟，遇到不同的硬币就进行翻转，可以发现翻转硬币数最少的方案是唯一的。

AC代码

#include<bits/stdc++.h>
using namespace std;int main() {string s1, s2;cin >> s1 >> s2;int ans = 0;for (int i = 0; i < s1.size() - 1; i++) {if (s1[i] != s2[i]) { //当前位置硬币正反不同，需要进行翻转s1[i] = s2[i];s1[i + 1] = s1[i + 1] == '*' ? 'o' : '*';ans++;}}cout << ans;return 0;
}

飞行员兄弟

题目描述

“飞行员兄弟”这个游戏，需要玩家顺利的打开一个拥有 16 个把手的冰箱。

已知每个把手可以处于以下两种状态之一：打开或关闭。

只有当所有把手都打开时，冰箱才会打开。

把手可以表示为一个 4×4 的矩阵，您可以改变任何一个位置 [i，j] 上把手的状态。

但是，这也会使得第 i 行和第 j 列上的所有把手的状态也随着改变。

请你求出打开冰箱所需的切换把手的次数最小值是多少。

输入格式

输入一共包含四行，每行包含四个把手的初始状态。

符号 + 表示把手处于闭合状态，而符号 - 表示把手处于打开状态。

至少一个手柄的初始状态是关闭的。

输出格式

第一行输出一个整数 N，表示所需的最小切换把手次数。

接下来 N 行描述切换顺序，每行输出两个整数，代表被切换状态的把手的行号和列号，数字之间用空格隔开。

注意：如果存在多种打开冰箱的方式，则按照优先级整体从上到下，同行从左到右打开。

数据范围

1 <= i，j <= 4

输入样例1:

-+--
----
----
-+--

输出样例1：

5

输入样例2:

*o**o***o***
*o***o**o***

输出样例2：

6
1 1
1 3
1 4
4 1
4 3
4 4

思路：

经分析可知：

• 每一个控制把手最多按一次

• 按把手的先后顺序无关紧要

• 本题很难找出递推规律，因为影响一个冰箱门的开关太多了，因此可以采用暴力枚举来解决

  • 枚举所有方案。0~2¹⁶ - 1（二进制枚举）每个方案对应的位置如下：

    0 1 2 3

    4 5 6 7

    8 9 10 11

    12 13 14 15

  • 按照每一个枚举的方案，对冰箱进行对应的操作

  • 判断方案是否符合要求

AC代码

#include<bits/stdc++.h>
using namespace std;const int N = 5;
char g[N][N], backup[N][N];int get(int x, int y) { //映射关系转换return x * 4 + y;
}void turn(int x, int y) { //将x，y所在位置的行和列的符号反转for (int i = 0; i < 4; i++) { //反转第x行的符号if (g[x][i] == '+') {g[x][i] = '-';} else {g[x][i] = '+';}}for (int i = 0; i < 4; i++) { //反转第y列的符号if (g[i][y] == '+') {g[i][y] = '-';} else {g[i][y] = '+';}}g[x][y] = g[x][y] == '+' ? '-' : '+';
}int main() {vector<pair<int, int>> ans; //用来存储当前最优的操作方案for (int i = 0; i < 4; i++) cin >> g[i];for (int i = 0; i < 1 << 16; i++) {vector<pair<int, int>> temp; //存储当前操作memcpy(backup, g, sizeof g); //备份//对当前方案进行检验for (int x = 0; x < 4; x++) {for (int y = 0; y < 4; y++) { //遍历矩阵if (i >> get(x,y) & 1) { //判断当前位置的开关是否被按temp.push_back({x, y});turn(x, y);}}}//判断所有冰箱是否都打开bool flag = true;for (int x = 0; x < 4; x++) {for (int y = 0; y < 4; y++) {if (g[x][y] == '+') {flag = false;}}}if (flag) {if (ans.empty() || ans.size() > temp.size()) { //记录操作次数最少的方案ans = temp;}}memcpy(g, backup, sizeof g); // 还原}cout << ans.size() << endl;for (int i = 0; i < ans.size(); i++) {cout << ans[i].first + 1 << " " << ans[i].second + 1 << endl;}return 0;
}