搜索，也就是对状态空间进行枚举，通过穷尽所有的可能来找到最优解，或者统计合法解的个数。——oi wiki
1.DFS 深度优先搜索
实现：递归（栈）
特点：不找到一个答案不回头
用途：可行性 找单个解等
个人所用模板如下：
2.BFS 广度优先搜索
实现：队列
特点：一层一层向下搜
用途：最短路等
个人所用模板如下：
例题：P1825 [USACO11OPEN]Corn Maze S
不难发现 实际上 dfs 与 bfs 的共同点 也是本人认为搜索的核心 即为“枚举能到达的所有状态” 使用搜索时 我们考虑的核心便是状态与如何进行状态转移 这点可以参考 dp 时设计状态与状态转移的思路
3.记忆化搜索
在暴力搜索中 同一状态可能会被重复搜索多次 浪费大量时间
这时我们就可以使用记忆化搜索 开一个 mem 数组记录已搜过的状态
传 世 经 典 ： P1048 [NOIP2005 普及组] 采药
我们以此题为例 介绍一下如何使用记忆化搜索
首先根据上面的 dfs 板子 很容易写出这样的暴力：
其中 x 表示当前物品编号 left 表示剩余时间
这时我们分析 dfs 时记录的状态 即编号 时间两个维度
那么我们的 mem 数组也开两个维度 记录已搜过的状态
最开始时初始化所有 mem 数组为 -1 即这个状态没有搜过
然后我们将函数返回值改为一个数 return时要返回 mem 数组的值
