什么是搜索？
搜索，是⼀种枚举，通过穷举所有的情况来找到最优解，或者统计合法解的个数。因此，搜索有时候也叫作暴搜。
搜索⼀般分为深度优先搜索(DFS)与宽度优先搜索(BFS)。
一、递归型枚举与回溯剪枝初识
回溯与剪枝
- 回溯：当在搜索的过程中，遇到⾛不通或者⾛到底的情况时，就回头。
- 剪枝：剪掉在搜索过程中，剪掉重复出现或者不是最优解的分⽀。
方法：
- 画决策树；
- 根据决策树写递归。
1. 枚举子集
题⽬来源：洛⾕
题⽬链接：B3622 枚举子集（递归实现指数型枚举） - 洛谷
难度系数：★
（1）题目描述
（2）算法原理
设⼀共有 个数，分别是 1 ≤n≤10 [1, 2, 3] 。 i Y 则表⽰第 名同学参加合唱；为 N 则表⽰ 。「从前往后」考虑每⼀个数，针对当前这个数「选」或者「不 选」，我们可以画出如下「决策树」：
设计递归函数：
- 重复⼦问题：针对某⼀位，「选」或者「不选」这个数。因为最终结果要按照「字典序」输出，我们可以「先考虑不选」，然后「再考虑选」；
- 实现⽅式参考代码和注释，结合「决策树」⼀起看会很清晰。
（3）参考代码
#include <iostream>using namespace std;int n;
string path; // 记录递归过程中，每一步的决策void dfs(int pos)
{if(pos > n){// path 就存着前 n 个人的决策cout << path << endl;return;}// 不选path += 'N';dfs(pos + 1);path.pop_back(); // 回溯，清空现场// 选path += 'Y';dfs(pos + 1);path.pop_back(); // 清空现场
}int main()
{cin >> n;dfs(1);return 0;
}2. 组合型枚举
题⽬来源：洛⾕
题⽬链接：P10448 组合型枚举 - 洛谷
难度系数：★
（1）题目描述
（2）算法原理
设 n =4,m=3 3 ，「从前往后」考虑 个位置应该选哪个数，我们可以画出如下决策树：
设计递归函数：
- 重复⼦问题：当前这⼀位，应该放哪个数上去。因为这是⼀个「组合」问题，不涉及排列，所以我 们当前位置开始放的数，应该是「上次决策的数的下⼀位」。
- 实现⽅式参考代码和注释，结合「决策树」⼀起看会很清晰。
（3）参考代码
#include <iostream>
#include <vector>using namespace std;int n, m;
vector<int> path;
// path.size();void dfs(int begin)
{if(path.size() == m){for(auto x : path) cout << x << " ";cout << endl;return;}for(int i = begin; i <= n; i++){path.push_back(i);dfs(i + 1);path.pop_back(); // 清空现场}
}int main()
{cin >> n >> m;dfs(1);return 0;
}3. 枚举排列
题⽬来源：洛⾕
题⽬链接：B3623 枚举排列（递归实现排列型枚举） - 洛谷
难度系数：★
（1）题目描述
（2）算法原理
设 n =3,k =2 ，⼀共要选出两个数，可以依次「考虑要选出来的数」是谁，画出如下决策树：
设计递归函数：
- 重复⼦问题：考虑这⼀位要放上什么数。因为是「排列」问题，所以我们直接从 开始枚举要放 的数。
- 剪枝：在这⼀条路径中，我们「不能选择之前已经选择过的数」。
- 实现⽅式参考代码和注释，结合「决策树」⼀起看会很清晰。
（3）参考代码
#include <iostream>
#include <vector>using namespace std;const int N = 15;int n, k;
vector<int> path;
bool st[N]; // 标记一下哪些数已经选过了void dfs()
{if(path.size() == k){for(auto x : path) cout << x << " ";cout << endl;return;}for(int i = 1; i <= n; i++){if(st[i]) continue;path.push_back(i);st[i] = true;dfs();// 恢复现场path.pop_back();st[i] = false;}
}int main()
{cin >> n >> k;dfs();return 0;
}4. 全排列问题
题⽬来源：洛⾕
题⽬链接：P1706 全排列问题 - 洛谷
难度系数：★
（1）题目描述
（2）算法原理
跟上⼀道题的决策⼀样，我们可以枚举每⼀位应该放上什么数，只不过少了 的限制。剪枝的策略还 是⼀样的，那就是在路径中，「不能选择之前已经选过的数」。
（3）参考代码
#include <iostream>
#include <vector>using namespace std;const int N = 15;int n;
bool st[N];
vector<int> path;void dfs()
{if(path.size() == n){for(auto x : path){printf("%5d", x);}cout << endl;return; }for(int i = 1; i <= n; i++){if(st[i]) continue;path.push_back(i);st[i] = true;dfs();// 恢复现场path.pop_back();st[i] = false;}
}int main()
{cin >> n;dfs();return 0;
}二、DFS
1. 选数
题⽬来源：洛⾕
题⽬链接：P1036 [NOIP 2002 普及组] 选数 - 洛谷
难度系数：★
（1）题目描述
（2）算法原理
「组合」型枚举，路径⾥⾯记录选择数的「总和」。在选出个数之后，判断「是否是质数」。
（3）参考代码
#include <iostream>using namespace std;const int N = 25;int n, k;
int a[N];int ret;
int path; // 记录路径中所选择的数的和bool isprime(int x)
{if(x <= 1) return false;// 试除法for(int i = 2; i <= x / i; i++){if(x % i == 0) return false;}return true;
}void dfs(int pos, int begin)
{if(pos > k){if(isprime(path)) ret++;return;}for(int i = begin; i <= n; i++){path += a[i];dfs(pos + 1, i + 1);path -= a[i]; // 恢复现场}
}int main()
{cin >> n >> k;for(int i = 1; i <= n; i++) cin >> a[i];dfs(1, 1);cout << ret << endl;return 0;
}2. ⻜机降落
题⽬来源：洛⾕
题⽬链接：P9241 [蓝桥杯 2023 省 B] 飞机降落 - 洛谷
难度系数：★★
（1）题目描述
（2）算法原理
枚举所有⻜机的「全排列」，判断是否存在⼀种排列，使的全部的⻜机都能安全降落。
剪枝：
- 当前路径⾥⾯只能选没有选过的⻜机；
- 如果这架⻜机不能正常降落，剪掉；
- 如果已经找到⼀种安全降落的⽅式，停⽌枚举，可以通过「递归的返回值」判断是否搜索成功。
（3）参考代码
#include <iostream>
#include <cstring>using namespace std;const int N = 15;int n;
int t[N], d[N], l[N];bool st[N]; // 标记路径中哪些飞机已经摆放过bool dfs(int pos, int end)
{if(pos > n){return true;}for(int i = 1; i <= n; i++){if(st[i] == true) continue; // 剪枝if(end > t[i] + d[i]) continue; // 剪枝int newend = max(t[i], end) + l[i];st[i] = true;if(dfs(pos + 1, newend)) return true;st[i] = false; // 回复现场}return false;
}int main()
{int T; cin >> T;while(T--) // 多组测试数据的时候，一定要注意清空数据{memset(st, 0, sizeof st);cin >> n;for(int i = 1; i <= n; i++) cin >> t[i] >> d[i] >> l[i];if(dfs(1, 0)) cout << "YES" << endl;else cout << "NO" << endl;}return 0;
}3. ⼋皇后
题⽬来源：洛⾕
题⽬链接：P1219 [USACO1.5] 八皇后 Checker Challenge - 洛谷
难度系数：★★
（1）题目描述
（2）算法原理
枚举策略：
- 「⼀⾏⼀⾏」的放皇后：从第⼀⾏开始，尝试在每⼀列上放皇后；
- 如果当前列放上皇后之后「没有冲突」，就标记⼀下这个「放法」，记录⼀下当前⾏的决策，然后 「递归」考虑下⼀⾏；
- 等到「所有⾏」都放置完毕之后，输出本次枚举的决策。
枚举策略应该是⽐较容易想到的，这道题的难点在于如何判断「在这⼀列放上这个皇后之后，是否冲突」。当我们⼀⾏⼀⾏放的时候，「⾏是不会产⽣冲突的」。产⽣冲突的只有「列」，「主对⻆
线」，以及「副对⻆线」。我们可以⽤三个数组分别标记：
- col[i] = true ，表⽰第 i ⾏放置了⼀个皇后；
- dig1[j − i + n] = true ，表⽰ y = x + (j − i) 这条「主对⻆线」上放置了⼀个皇后；
- dig2[j + i] = true ，表⽰ y = −x + (j + i) 这条「副对⻆线」上放置了⼀个皇后。
（3）参考代码
#include <iostream>
#include <vector>using namespace std;const int N = 15;int n;
bool col[N], st1[N * 2], st2[N * 2];int ret;
vector<int> path;void dfs(int x)
{if(x > n){ret++;if(ret <= 3){for(auto x : path) cout << x << " ";cout << endl;}return;}for(int y = 1; y <= n; y++){// 判断能不能摆在这一列if(col[y] || st1[y - x + n] || st2[y + x]) continue; // 剪枝col[y] = st1[y - x + n] = st2[y + x] = true;path.push_back(y);dfs(x + 1);col[y] = st1[y - x + n] = st2[y + x] = false;path.pop_back();}
}int main()
{cin >> n;dfs(1);cout << ret << endl;return 0;
}4. 数独
题⽬来源：洛⾕
题⽬链接：P1784 数独 - 洛谷
难度系数：★★
（1）题目描述
（2）算法原理
枚举策略：
- 「⼀个格⼦⼀个格⼦」往⾥⾯填数。
- 从第⼀⾏的第⼀个格⼦开始，填上⼀个「没有冲突」的数，然后「递归」到下⼀个格⼦；
- 当某⼀⾏填满之后，递归到「下⼀⾏的起始位置」继续填数。
可以创建三个数组，⽤来帮助判断填上某⼀个数之后，是否会发⽣冲突。对于3 × 3⽅格，我们可以给每⼀个格⼦编上号，快读定位，如下图：
- row[i][num] = true 表⽰：第 i ⾏已经放上了列已经放上了 num 这个数；
- col[j][num] = true 表⽰：第 j 列已经放上了列已经放上了 num 这个数；
- st[i / 3][j / 3][num] = true 表⽰：[i / 3, j / 3] 的 3 × 3 ⽅格⾥，已经放上了 num 这个数。
（3）参考代码
#include <iostream>using namespace std;const int N = 10;int n = 9;
int a[N][N];
bool row[N][N], col[N][N], st[N][N][N];bool dfs(int i, int j)
{if(j == n) {// 当这一行填满之后i++;j = 0;}if(i == n) return true; // 找到一种合法的情况，就停止递归if(a[i][j]) return dfs(i, j + 1);for(int x = 1; x <= 9; x++){if(row[i][x] || col[j][x] || st[i / 3][j / 3][x]) continue; // 剪枝row[i][x] = col[j][x] = st[i / 3][j / 3][x] = true;a[i][j] = x;if(dfs(i, j + 1)) return true;// 恢复现场row[i][x] = col[j][x] = st[i / 3][j / 3][x] = false;a[i][j] = 0; }return false;
}int main()
{for(int i = 0; i < n; i++){for(int j = 0; j < n; j++){cin >> a[i][j];int x = a[i][j];if(x){// 标记一下row[i][x] = col[j][x] = st[i / 3][j / 3][x] = true;}}}dfs(0, 0);for(int i = 0; i < n; i++){for(int j = 0; j < n; j++){cout << a[i][j] << " ";}cout << endl;}return 0;
}三、剪枝与优化
剪枝，形象得看，就是剪掉搜索树的分⽀，从⽽减⼩搜索树的规模，排除掉搜索树中没有必要的分 ⽀，优化时间复杂度。
在深度优先遍历中，有⼏种常⻅的剪枝⽅法：
- 1. 排除等效冗余
如果在搜索过程中，通过某⼀个节点往下的若⼲分⽀中，存在最终结果等效的分⽀，那么就只需要搜 索其中⼀条分⽀。
- 2. 可⾏性剪枝
如果在搜索过程中，发现有⼀条分⽀是⽆论如何都拿不到最终解，此时就可以放弃这个分⽀，转⽽搜 索其它的分⽀。
- 3. 最优性剪枝
在最优化的问题中，如果在搜索过程中，发现某⼀个分⽀已经超过当前已经搜索过的最优解，那么这 个分⽀往后的搜索，必定不会拿到最优解。此时应该停⽌搜索，转⽽搜索其它情况。
- 4. 优化搜索顺序
在有些搜索问题中，搜索顺序是不影响最终结果的，此时搜索顺序的不同会影响搜索树的规模。 因此，应当先选择⼀个搜索分⽀规模较⼩的搜索顺序，快速拿到⼀个最优解之后，⽤最优性剪枝剪掉 别的分⽀。
- 5. 记忆化搜索
记录每⼀个状态的搜索结果，当下⼀次搜索到这个状态时，直接找到之前记录过的搜索结果。 记忆化搜索，有时也叫动态规划。
1. 数的划分
题⽬来源：洛⾕
题⽬链接：P1025 [NOIP 2001 提高组] 数的划分 - 洛谷
难度系数：★★
（1）题目描述
（2）算法原理
搜索策略：
- 将 [1, n] 个数放在 k 个坑⾥⾯，使的坑⾥⾯的所有数的总和是 n ；
- 其中，不同的坑⾥⾯的数可能相同；
- 但是 [1, 2] 与 [2, 1] 是同⼀种分法，因此，应该是⼀种组合型枚举。针对每⼀个坑⾥⾯的数应该放谁的时候，应该从上⼀个坑⾥⾯的数开始枚举。
剪枝策略：
- 当我们填了 cnt 个坑时，此时总和是 sum ，如果后续坑位全部都填上最⼩值都会超过 n 。说明我们之前填的数太⼤了，导致后⾯怎么填都会超过 n ，直接剪掉。
注意剪枝位置的不同，⽽导致搜索树的不同：
- 如果在进⼊递归之前剪枝，我们不会进⼊⾮法的递归函数中；
- 但是如果在进⼊递归之后剪枝，我们就会多进⼊很多不合法的递归函数中。
（3）参考代码
#include <iostream>using namespace std;int n, k;
int path, ret;void dfs(int pos, int begin)
{if(pos == k){if(path == n) ret++;return;}// 可行性剪枝// if(path + begin * (k - pos) > n) return;for(int i = begin; i <= n; i++){// 可行性剪枝if(path + i * (k - pos) > n) return;path += i;dfs(pos + 1, i);path -= i;}
}int main()
{cin >> n >> k;dfs(0, 1);cout << ret << endl;return 0;
}2. ⼩猫爬⼭
题⽬来源：洛⾕
题⽬链接：P10483 小猫爬山 - 洛谷
难度系数：★★
（1）题目描述
（2）算法原理
搜索策略：依次处理每⼀只猫，对于每⼀只猫，我们都有两种处理⽅式：
- 要么把这只猫放在已经租好的缆⻋上；
- 要么重新租⼀个缆⻋，把这只猫放上去。
剪枝：
- 在搜索过程中，我们⽤全局变量记录已经搜索出来的最⼩缆⻋数量。如果当前搜索过程中，已经⽤的缆⻋数量⼤于全局记录的最⼩缆⻋数量，那么这个分⽀⼀定不会得到最优解，剪掉。
- 优化枚举顺序⼀：从⼤到⼩安排每⼀只猫
- 重量较⼤的猫能够快速把缆⻋填满，较快得到⼀个最⼩值；
- 通过这个最⼩值，能够提前把分⽀较⼤的情况提前剪掉。
- 优化枚举策略⼆：先考虑把⼩猫放在已有的缆⻋上，然后考虑重新租⼀辆⻋
因为如果反着来，我们会先把缆⻋较⼤的情况枚举出来，这样就起不到剪枝的效果了
（3）参考代码
#include <iostream>
#include <algorithm>using namespace std;const int N = 20;int n, w;
int c[N]; // 小猫的信息int cnt; // 当前用了多少车
int s[N]; // 每一辆车目前的总重int ret = N; // 最优解bool cmp(int a, int b)
{return a > b;
}void dfs(int pos)
{// 策略二：最优性剪枝if(cnt >= ret) return;if(pos > n){ret = cnt;return;}// 策略三：优化搜索顺序// 先安排在已有的车辆上for(int i = 1; i <= cnt; i++){// 策略一：可行性剪枝if(s[i] + c[pos] > w) continue;s[i] += c[pos];dfs(pos + 1);s[i] -= c[pos]; // 恢复现场}// 重开一辆车cnt++;s[cnt] = c[pos];dfs(pos + 1);// 恢复现场s[cnt] = 0;cnt--;
}int main()
{cin >> n >> w;for(int i = 1; i <= n; i++) cin >> c[i];// 策略三：优化搜索顺序sort(c + 1, c + 1 + n, cmp);dfs(1);cout << ret << endl;return 0;
}四、记忆化搜索
记忆化搜索也是⼀种剪枝策略。
通过⼀个"备忘录"，记录第⼀次搜索到的结果，当下⼀次搜索到这个状态时，直接在"备忘录"⾥⾯找结果。
记忆化搜索，有时也叫动态规划。
1. 斐波那契数
题⽬来源：⼒扣
题⽬链接：509. 斐波那契数 - 力扣（LeetCode）
难度系数：★
（1）题目描述
（2）算法原理
在搜索的过程中，如果发现特别多完全相同的⼦问题，就可以添加⼀个备忘录，将搜索的结果放在备忘录中。下⼀次在搜索到这个状态时，直接在备忘录⾥⾯拿值。
（3）参考代码
class Solution
{int f[35]; // 搞⼀个备忘录
public:int fib(int n)
{memset(f, -1, sizeof f); // 先初始化成⼀定不会存在的值return dfs(n);
}int dfs(int n){// 搜索之前先往备忘录⾥⾯瞅瞅if(f[n] != -1) return f[n];if(n == 0 || n == 1) return n;// 返回之前，把结果记录在备忘录中f[n] = dfs(n - 1) + dfs(n - 2);return f[n];}};2. Function
题⽬来源：洛⾕
题⽬链接：P1464 Function - 洛谷
难度系数：★
（1）题目描述
（2）算法原理
题⽬叙述的⾮常清楚，我们仅需按照「题⽬的要求」把「递归函数」写出来即可。但是，如果不做其余处理的话，结果会「超时」。因为我们递归的「深度」和「⼴度」都⾮常⼤。
通过把「递归展开图」画出来，我们发现，在递归过程中会遇到⼤量「⼀模⼀样」的问题，如下图
（因为递归展开过于庞⼤，这⾥只画出了⼀部分）：
因此，可以在递归的过程中，把每次算出来的结果存在⼀张「备忘录」⾥⾯。等到下次递归进⼊「⼀模⼀样」的问题之后，就「不⽤傻乎乎的展开计算」，⽽是在「备忘录⾥⾯直接把结果拿出来」，起到⼤量剪枝的效果。
（3）参考代码
#include <iostream>using namespace std;typedef long long LL;const int N = 25;LL a, b, c;
LL f[N][N][N]; // 备忘录LL dfs(LL a, LL b, LL c)
{if(a <= 0 || b <= 0 || c <= 0) return 1;if(a > 20 || b > 20 || c > 20) return dfs(20, 20, 20);if(f[a][b][c]) return f[a][b][c];if(a < b && b < c) return f[a][b][c] = dfs(a, b, c - 1) + dfs(a, b - 1, c - 1) - dfs(a, b - 1, c);else return f[a][b][c] = dfs(a - 1, b, c) + dfs(a - 1, b - 1, c) + dfs(a - 1, b, c - 1) - dfs(a - 1, b - 1, c - 1);
}int main()
{while(cin >> a >> b >> c){// 多组测试数据：不需要清空if(a == -1 && b == -1 && c == -1) break;printf("w(%lld, %lld, %lld) = %lld\n", a, b, c, dfs(a, b, c)); }return 0;
}3. 天下第⼀
题⽬来源：洛⾕
题⽬链接：P5635 【CSGRound1】天下第一 - 洛谷
难度系数：★★
（1）题目描述
（2）算法原理
⽤递归模拟整个游戏过程： dfs(x, y) 的结果可以由 dfs((x + y) % p, (x + y + y) % p) 得到。
因为测试数据是多组的，并且模数都是 p ，再加上递归的过程中会递归的相同的问题，所以可以把递归改写成记忆化搜索。
- f [x][y] = 1 ，表⽰ cbw 赢；
- f [x][y] = 2 ，表⽰ zhouwc 赢；
- f [x][y] = 3 ，表⽰这个位置已经被访问过，如果没被修改成 1 或者 2 ，那就表明平局。
注意事项：
- 这道题的数据范围很⼤，⽤ int 类型创建⼆维数组空间会溢出。但是我们的最终结果仅有三种情况，所以可以⽤ char 类型来存储最终结果，节省空间。
（3）参考代码
#include <iostream>using namespace std;const int N = 1e4 + 10;int x, y, p;
char f[N][N]; // 备忘录char dfs(int x, int y)
{if(f[x][y]) return f[x][y]; // 剪枝f[x][y] = '3'; // 这个状态已经访问过了，之后再遇到时，表示平局if(x == 0) return f[x][y] = '1';if(y == 0) return f[x][y] = '2';return f[x][y] = dfs((x + y) % p, (x + y + y) % p);
}int main()
{int T; cin >> T >> p;while(T--){cin >> x >> y;char ret = dfs(x, y);if(ret == '1') cout << 1 << endl;else if(ret == '2') cout << 2 << endl;else cout << "error" << endl;}return 0;
}3. 滑雪
题⽬来源：洛⾕
题⽬链接：P1434 [SHOI2002] 滑雪 - 洛谷
难度系数：★★
（1）题目描述
（2）算法原理
暴⼒枚举：遍历整个矩阵，看看以当前位置为起点，最远能滑⾏多远的距离。在所有情况⾥⾯，取最⼤值即可。
如何求出以 [i, j] 为起点的最⼤距离？
- 从 [i, j]位置上下左右瞅⼀瞅，如果能滑过去，就看看以下⼀个位置为起点，最远能滑⾏多远的距离；
- 找出四个⽅向上的最远距离，然后 +1 。 因为出现相同⼦问题，所以可以⽤ dfs 来解决。⼜因为在搜索的过程中会遇到⼀模⼀样的问题，因此可以把递归改成记忆化搜索的⽅式。
（3）参考代码
#include <iostream>using namespace std;const int N = 110;int n, m;
int a[N][N];
int f[N][N]; // 备忘录int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};int dfs(int i, int j)
{if(f[i][j]) return f[i][j];int len = 1;// 上下左右四个方向搜for(int k = 0; k < 4; k++){int x = i + dx[k], y = j + dy[k];if(x < 1 || x > n || y < 1 || y > m) continue;if(a[i][j] <= a[x][y]) continue;len = max(dfs(x, y) + 1, len);}return f[i][j] = len;
}int main()
{cin >> n >> m;for(int i = 1; i <= n; i++)for(int j = 1; j <= m; j++)cin >> a[i][j];int ret = 1;for(int i = 1; i <= n; i++)for(int j = 1; j <= m; j++)ret = max(ret, dfs(i, j));cout << ret << endl;return 0;
}
