正文篇
第三章 DFS 题目的复杂度优化
$3.1$ DFS 剪枝
五种剪枝类型
1、可行性剪枝
所谓可行性剪枝，顾名思义，就是当当前状态和题意不符，并且由于题目可以推出，往后的所有情况和题意都不符，那么就可以进行剪枝，直接把这种情况及后续的所有情况判负，直接返回。
即：不可行，就返回。
2、排除等效冗余
所谓排除等效冗余，就是当几个枝丫具有 完全相同的效果 的时候，只选择其中一个走就可以了。
即：都可以，选一个。
3、最优性剪枝
所谓最优性剪枝，是在我们用搜索方法解决最优化问题的时候的一种常用剪枝。就是当你搜到一半的时候，已经比 搜到的最优解要不优了，那么这个方案肯定是不行的，即刻停止搜索，进行回溯。
即：有比较，选最优。
4、顺序剪枝
普遍来讲，搜索的顺序是不固定的，对一个问题来讲，算法可以进入搜索树的任意的一个子节点。但假如我们要搜索一个最小值，而非要从最大值存在的那个节点开搜，就可能存在搜索到最后才出解。而我们从最小的节点开搜很可能马上就出解。这就是顺序剪枝的一个应用。一般来讲，有单调性存在的搜索问题可以和贪心思想结合，进行顺序剪枝。
即：有顺序，按题意。
5、记忆化
记忆化搜索其实是搜索的另外一个分支。在这里简单介绍一下记忆化的原理：
就是记录搜索的每一个状态，当 重复搜索到相同的状态 的时候直接返回。
即：搜重了，直接跳。
例题解析
这出现频率才配得上 $DFS$ 中最为经典的题目之一。
可行性剪枝 ： 木棒总长度不能整除目标木棒的长度
排除等效冗余 ：
如果这些木棒已经拼出了其中的一个目标木棒，就不用再管这些木棒了。
如果用一个木棒拼目标木棒失败了，就不用考虑与其等长的木棒了。
最优性剪枝 ： 如果当前拼出的木棒长度大于目标木棒长度，不满足。
顺序剪枝 ： 从大到小枚举木棒，可以减少深层子树大小。
同样是非常经典的题目，也是一道剪枝好题。
由于数独2里 横、竖、十六宫格中 1~16 都只出现一次，
排除等效冗余 ： 填可能性最小的空格。
常数优化 ： 采用二进制解决。
其难点主要是对数独二进制的表示，思路上还是很简单的。
这是一道 NPC问题， 记得在状态转换的时候备份啊。
$3.2$ DFS 记忆化搜索
记忆化搜索其实是搜索的另外一个分支。在这里简单介绍一下记忆化的原理：
就是记录搜索的每一个状态，当 重复搜索到相同的状态 的时候直接返回。
即：搜重了，直接跳。
记忆化搜索的适用性很广，可以解决几乎所有的 $DP$问题，这在 $1.4$ 中就已经做过详细介绍。
所以，让我们直接开始上手做题吧！
状态简化 ： 只维护村子的四个角落， 证明
记忆化搜索 ： 在天数、当前云位置、四个角落离上一次降雨的天数相同时，可以直接取用，证明
常数优化 ： 布尔关系可用二进制表示，证明
本题的难点是对冗余 $K$ 的处理。
面对这一类状态空间过大的问题，最好的解决方式就是将其缩小。
所以 路径长 $<= d + K$ 可以转化成 $= {d, d + 1, d + 2, …, d + K}$
现在的问题就是如何处理 $= {d + c}$ 时满足要求的路径条数了。
这里会用记忆化搜索的方式解决。
1、解决顺序与方式
这里采用的方式是 逆推求满足性，
即先确定从起点到终点所用的冗余，再根据不同的出边转换，用反向 $Dijkstra$，快速求出出边会产生的冗余，
从而计算此后节点会产生的冗余。
注意此方法有 两个边界
【1】到达终点、没有冗余
【2】当前冗余已大于起点到终点的冗余、此后无论如何都不满足（可行性剪枝）
2、记忆化搜索 在状态相等时可以使用，如结点相同、冗余相同则方案数也相同
3. 标记数组判零环
因为 $0$ 环不会增加冗余，所以同一个冗余重复搜到了同一个结点，就代表有 $0$ 环。
但需要注意的是，即使没有 $0$ 环，也可能会有两条同冗余路径交到同一结点，这种情况怎么避免呢？
注意 $DFS$ 一条道走到黑的性质，如果在同一条链上重复搜到则是零环造成，反之则不是。
所以我们要在搜完了这条链之后解除标记。
还是挺简单哒！（也就调了一上午嘛
$3.3$ DFS 启发式搜索
启发式搜索是一种可以通过当前信息推断走哪一步最有希望搜到正确答案的算法。
想要灵活运用启发式搜索，最核心的就是学会设计估价函数，即一个可以预估未来代价的函数。
* 估价函数的设计
设计估价函数的最重要的一点就是它一定要比真实情况 更优。
因为，如果它劣于真实情况，则有可能会让正确答案一直压底，从而得到一个错误的结果。
其次，估价函数的更新必须是在线的，也就是说，在搜索过程中，估价函数要随之更新。
通常都是采取 预处理 或 找规律 的方式设计估价函数。
* 估价函数的使用方式
首先要明确估价函数的作用 排除无用解 和 找到最优解。
如果可以确定 目标状态大小 就可以通过 排除无用解 来进行剪枝，这也被称为 $IDA*$
当然也可以通过一些动态处理 $max/min$ 的数据结构，如堆、线段树、平衡树，
来 优先 更新 当前值 $+$ 期望值 最优的解。
$DFS$ 常用 $IDA*$，即迭代法 $+$ 启发式解决，若搜索层数过深，也可以改用二分。
$BFS$ 等最短路算法则常用 $A*$，可以方便的进行动态更新。
但相较而言，$IDA*$ 要更好写一些。
看到此题，我们先分析一下搜索框架。
枚举的分支是书抽出时的 首尾位置 和 插入的位置，记得在每一次搜索完后回溯，搜索新的分支。
因为搜索树的深度最多为 $5$，所以可以定义一个 $w[5][N]$ 的数组来记录原顺序（零步、一步、两步…）。
然后就是预估函数的处理了，请看下图：
1 2 [4 5] 3 | 6
=> 1 2 3 4 5 6
此图意思是将 $4,5$ 移到 $3$ 的后面。
这一个操作更改了 $2, 3, 5$ 三数的后效数字，是移数增加答案的 最优情况，也是本题预估函数的公式。
即，错位数 $/ 3 $的上取整。
