正文篇
第一章 引言
$1.1$ DFS 的定义
* DFS 的基层实现原理
$DFS$ 即 深度优先搜索，在程序中是以 栈的形式 实现，符合 栈 的先进先出的原理，当栈不为空时，就会一直弹出栈顶元素。
这也是 $DFS$ 在实现时，会一直往一条道上搜， 直到搜完才返回的原因。
但是，如果 $DFS$ 在第一次搜完之后就结束了， 那么作用不大，但是如果在 每一次递归 (即压栈) 的时候
同时递归其它值， 由于递归其它值的操作只有在 上一条道搜完之后 才会执行，所以会在一些深度上形成分叉。
只要能够 确认问题的搜索框架，就可以 穷举所有方案，也就是 一切皆可搜 的由来。
* DFS 的实现场景
$DFS$ 是一种用递归实现的算法，但本质上完全可以借助栈来解决。
常见的深度优先搜索的应用分别是 图的连通性模型、枚举方案数、枚举所有可能性、 树的自底向上维护信息 等等，
这些都会在后文作详细介绍。
* DFS 的实现方式
那 $DFS$ 又应该如何实现呢？
其中的难点在于对题目要求的转换和对无用的状态空间的排除，
在此，给出一些最基本的 $DFS$ 代码实现和最基本的思想讲解。
设计一个 $DFS$ 代码，你要确定在你的搜索树中你要 维护那些信息，以及你往下搜索的扩展方式。
一定要尽量吝啬于你 往外延伸的分支数量，不然时间复杂度会以一个极为恐怖的方式增长。
void dfs(变化的参数, 如深度、方案数、枚举到第几个方案、横纵坐标等等)
{
if 问题边界 // 必备的, 只有有限的空间才可以搜索
{
维护答案;
return;
}
往不同方向搜索延伸 // 搜索分支
{
dfs(参数发生不同的变化); // 往下搜索
}
}
这是一个最基本的框架，也是后文延伸的一个基础，抱着循序渐进的想法，更多内容就留给下文阐述。
* 回溯法的原理
回溯法 是系统地搜索问题状态的方法。
某个问题的 所有可能状态 称为问题的 状态空间，若 状态空间是有限的，便可将状态空间映射成 树结构。
请记住，任何状态空间可以映射成树结构的问题，都可以使用回溯法。
也就是说，回溯法是能够在树结构里搜索到 通往特定终点 的一条或者多条特定路径。
回溯算法的基本思想是：
"从一条路往前走，能进则进，不能进则退回来，换一条路再试，从而搜索到抵达特定终点的一条或者多条特定路径。"
值得注意，回溯法以深度优先搜索的方式搜索 状态空间，并且在搜索过程中 用剪枝函数避免无效搜索。
那么，它可以解决哪些题目呢？
-
【组合问题】：N个数里面按一定规则找出k个数的集合
-
【排列问题】：N个数按一定规则全排列，有几种排列方式
-
【切割问题】：一个字符串按一定规则有几种切割方式
-
【子集问题】：一个N个数的集合里有多少符合条件的子集
-
【棋盘问题】：N皇后，解数独等等
在回溯法的题目里，我们的模板也有了一些变化。
void dfs(变化的参数, 如深度、方案数、枚举到第几个方案、横纵坐标等等)
{
if 问题边界 // 必备的, 只有有限的空间才可以搜索
{
维护答案;
return;
}
往不同方向搜索延伸 // 搜索分支
{
处理此节点信息
dfs(参数发生不同的变化); // 往下搜索
复原此节点信息, 才可以进行对分支的正确搜索。 // 回溯
}
}
为什么这样就可以遍历整个搜索树呢？
感性的理解是：for循环可以理解是横向遍历，dfs（递归）就是纵向遍历
同样，也可以画图体会。
多数问题都需要靠回溯法来求解，但必须要强调的是
深度优先搜索 不等于 回溯法
正如上文所述，回溯法解决的是 树形结构 问题，
而深度优先搜索同样也可以用于 图结构 问题
当问题不在只是一棵树的时候，可能会存在 例如 环、重边 等更复杂的结构。
更重要的是这类问题 一个节点需要且只需访问一次。
为了解决重复遍历的问题，我们往往会用一个 $st$ 数组来储存图的某个节点是否重复遍历的问题。
而不再继续使用回溯法了，毕竟你要走的路径已经给出了呀。
$1.2$ DFS 的可传递信息
*DFS 自底向上的信息维护
深搜作为一种实用的算法，可以维护几乎所有的信息，但笔者能力有限，故此，仅列举几种常用信息的维护方式。
$【sum$ 值的维护】 ：
我们用一个 $sum$ 数组储存 以这个节点为根的子树之和，同时用一个 $st$ 数组储存 树的某个节点是否被重复遍历。
然后，我们就可以遍历整棵树了。
可以看出，从一个节点出发往下的所有节点都是它的子树。
因此，我们仅需要在往下搜索时，储存一个变量 $sum$, 在返回的过程中维护以它为根的子树之和，往上传递时，其父节点仅需要加上它的值就可以了。
这也是一个名为 打包 的重要思想。
【树的最小字典序维护】 ：
给定你一颗树，让你求出在可以重复经过同一个节点的情况下，遍历所有节点的字典序最小的方案是什么？
字典序仅会在第一次到达此节点时累计。
我们用一个 $path$ 数组储存方案，先将每一个点的出边排序，从字典序小的边开始搜，并维护第一次搜到的点的方案。
同样用 $st$ 数组判重，由于 DFS 一次搜到底的性质，在不存在环的情况下满足
运用贪心的思想，由字典序从小到大遍历整棵树，一点是最优的。
【树的重心】 ：
重心是指树中的一个结点，如果将这个点删除后，剩余各个连通块中子节点数的最大值最小，那么这个节点被称为树的重心。
将一颗树的一个节点删掉后，树会被分成两个部分，可维护的值有两个。
一个是以它为根的下一层子树中最大的一颗的子节点数，一个是除去以它为根的子树后剩余节点数。
根据容斥原理，直接维护最大联通子图的节点数即可。
$1.3$ DFS 的铺垫知识
*前提条件
当 原问题 与 问题边界 之间的 每个变换步骤具有相似性时 就可以考虑用 递归 或 递推 来求解
*变换步骤（递归）
对于递归算法，可以通过以下三个操作来求解
1. 【自身调用自身】
缩小问题规模空间 ，
这意味着程序尝试寻找在 原问题 与 问题边界 之间的 变化路线，并向 正在探索 的路线上迈出一步
2. 【回溯时还原现场（搜索失败）】
尝试求解 规模缩小以后的问题，
如果失败，程序需要 重新回到当前问题 去寻找 其它的变换路线，
因此把 当前问题 缩小为 子问题 时所做的 对当前问题状态产生影响的事情 应 全部失效
3. 【扩展（搜索成功）】
找到了 规模缩小以后的问题 的答案， 那么将答案 扩展到当前问题。
如果失败，就 重新返回 当前问题，继续寻找 当前答案 的 其它变换路线，直至 确定当前问题无法求解
总结
简洁的说，就是 缩小，求解，扩展
*DFS 的三种枚举方式
【指数型枚举】 ：
对于序列中每个整数都有两种可能，选 或者 不选
也就是说，这颗搜索树上的每一个节点都有两个分支，
每次将尚未确定的整数减少 $1$，从而转换成一个更小的同类问题。
注意：指数型枚举不考虑顺序
时间复杂度 $O(k^n)$
注意：其中的 $k$ 为常数。
void dfs(int u){
if (u == n + 1)
{
for (int i = 0; i < ch.size(); i ++ )
printf("%d ", ch[i]);
puts("");
return;
}
dfs(u + 1);
ch.push_back(u);
dfs(u + 1);
ch.pop_back();
}
【组合型枚举】 ：
可以等价于上述枚举仅在 枚举数 $= m$ 的情况下有效。
注意：组合型枚举不考虑顺序
时间复杂度 $O(C_n^m)$
组合数的知识会在 数论 一章进行讲解
void dfs(int u){
if (ch.size() > m || ch.size() + (n - u + 1) < m) return;
if (u == n + 1)
{
for (int i = 0; i < ch.size(); i ++ )
printf("%d ", ch[i]);
puts("");
return;
}
dfs(u + 1);
ch.push_back(u);
dfs(u + 1);
ch.pop_back();
}
【排列型枚举】 ：
它与组合型枚举的最大不同在于它考虑搜索顺序。
它的搜索树分支是这样的 ：
可以看出，第一层每个数有三个分支，第二层每个数有两个分支，第三层每个数有一个分支。
也就是说，这个搜索树的分支具有收敛性。
这中枚举的功能是 其中的每个分支都是在当前未选择的数中挑选一个，具体可以看图。
时间复杂度 $O(P_n^m)$
int st[N];//存储方案
bool used[N];//标记数字是否被用过，true表示被用过，false表示没被用过
int n;
void dfs(int u) { //当前枚举第u位
if (u > n) {
for (int i = 1; i <= n; i ++ )
printf("%d ", st[i]); //打印方案
puts("");
return ;
}
for (int i = 1; i <= n; i ++ ) { //依次枚举每个数
if (!used[i]) { //当前数可用
st[u] = i;
used[i] = true;
dfs(u + 1);
//恢复现场
st[u] = 0; //可省略
used[i] = false;//不可省
}
}
}
int main() {
scanf("%d", &n);
dfs(1);
return 0;
}
$1.4$ 记忆化搜索初步
1.记忆化搜索的思想
在搜索过程中，会有很多重复计算，如果我们能记录一些状态的答案，就可以减少重复搜索量
2、记忆化搜索的适用范围
根据记忆化搜索的思想，它是 解决重复计算，而不是重复生成
也就是说，这些搜索必须是在 搜索 扩展路径的过程中分步计算的题目，也就是“搜索答案与路径相关”的题目，而不能是 搜索一个路径之后才能进行计算的题目，
必须要分步计算，并且搜索过程中，一个搜索结果必须可以建立在 同类型问题 的结果上，也就是类似于动态规划解决的那种。
也就是说，他的问题表达，不是 单纯生成一个走步方案，而是生成一个走步方案的代价等，而且每走一步，在 搜索树/图 中生成一个新状态，都可以精确计算出到此为止的费用。
也就是，可以分步计算，这样才可以 套用已经得到的答案
3、记忆化搜索的核心实现
$a.$ 首先，要通过一个表 记录已经存储下的搜索结果，一般用 哈希表 实现
$b.$ 状态表示，由于是要用 哈希表 实现，所以状态最好可以用数字表示，常用的方法是把一个状态连写成一个 $p$ 进制数字，然后把这个数字对应的十进制数字作为状态
$c.$ 在每一状态搜索的开始，高效的使用哈希表搜索这个状态是否出现过，如果已经做过，直接调用答案，回溯
$d.$ 如果没有，则按正常方法搜索
