使用场景
输入数据：如果是递归数据结构，如单链表，二叉树，集合，则一定可以用DFS；如果是非递归数据结构，如一维数组，二维数组，字符串，图，则概率小一点。
状态转换图：树或图
求解目标：必须要走到最深（如树，必须走到叶结点）才能得到一个解，这种情况适合用DFS
思考的步骤
1.是求路径条数，还是路径本身(或动作序列)？
DFS最常见的三个问题，求可行解的总数，求一个可行解，求所有可行解。
（a）如果是路径条数，则不需要存储路径
（b）如果是求路径本身，则要用一个数组path[]存储路径。和BFS不同，BFS虽然最终求的也是一条路径，但需要存储扩展过程的中所有路径，在没有找到答案之前所有路径都不能放弃；而DFS，在搜索过程中始终只有一条路径，因此用一个数组就足够了。
2.只要求一个解，还是要求所有解？
如果只要求一个解，那就找到一个解就可以返回
如果要求所有解，找到一个后，还要继续扩展，知道遍历完
BFS一般只要求一个解，因此不需要考虑这个额问题(BFS当然也可以求所有解，这时需要扩展到所有叶子结点，相当于在内存中存储整个状态转换图，非常占内存，因此BFS不适合解这类问题)
3.如何表示状态？
即一个状态需要存储那些必要的数据，才能完整提供如何扩展到下一步状态的所有信息。和BFS不同，DFS的惯用写法，不是把数据记录在状态struct里，而是添加函数参数（有时为了节省递归堆栈，用全局变量），struct里的字段与函数参数一一对应。
4.如何扩展状态？
这一步和上一步相关。状态里记录得数据不同，扩展方法也就不同。对于固定不变的数据结构（一般题目直接给出，作为输入数据），如二叉树，图等，扩展方法很简单，直接往下一层走，对于隐式图，要先在第一步里想清楚状态所带的数据。
5.关于判重
（a）是否需要判重？如果状态转换图是一棵树，则不需要判重，因为在遍历过程中不可能重复；如果状态转换图是一个DAG，则需要判重。这一点和BFS不同，BFS的状态转换图总是DAG，必须要判重。
（b）怎样判重？和BFS相同！！同时DAG说明存在重叠子问题，此时可以用缓存加速。
6.终止条件是什么？
终止条件是指到了不能扩展的末端节点。对于树，是叶子结点，对于图或者隐式图，是出度为0的节点
7.收敛条件是什么？
收敛条件是指找到了一个合法解的时刻。如果是正向DFS（父状态处理完才进行递归，即父状态不依赖子状态，递归语句一定是在最后，尾递归），则是指是否达到目标状态；如果是逆向DFS（处理父状态时需要先知道子状态的结果，此时递归语句不在最后），则是指是否达到初始状态。
由于很多时候终止条件和收敛条件是合二为一的，因此很多人不区分这两种条件。仔细区分这这两种条件是很有必要的。
为了判断是否到了收敛条件，要在函数接口里面用一个参数记录当前的位置（或距离目标还有多远）。如果是求一个解，直接返回这个解；如果是求所有解，要在这里收集解，即把第一步中表示路径的数组path[]复制到解集合里面。
8.如何加速？
（a）剪枝。 无通用方法，具体分析，在中间节点提前返回。
（b）缓存。
i。提前条件：状态转换图是一个DAG.DAG--》存在重叠子问题--》子问题的解会被重复利用，用缓存能加速。如果依赖关系是树状的（如树，单链表等），没有必要加缓存，因为子问题只会一层层往下，用一次就再也不会用到，加了缓存也没有啥加速效果。
ii。具体实现：可以用数组/HashMap。维度复杂的，用HashMap，C++有map，C++11以后用unordered_map，比map快。
拿到一个题目，回忆上面8个问题，对于树，不需要回答第5和第8个问题。
------------------------------------------------------------------------------------------
dfs模板
*input 输入数据指针
*path 当前路径，也是中间结果
*result存放最终结果
*cur/gap标记当前位置/距离目标的距离
*return 路径长度，如果是求路径本身，则不需要返回长度
/** *dfs模板 *input 输入数据指针 *path 当前路径，也是中间结果 *result存放最终结果 *cur/gap标记当前位置/距离目标的距离 *return 路径长度，如果是求路径本身，则不需要返回长度 */ void dfs(type &input,type &path,type &result ,int cur or gap){ if(数据非法) return 0;//终止条件 if(cur==input.size()){//收敛条件 //if(gap==0){ 将path放入result } if(可以剪枝) return; for(...){//执行所有可能的扩展动作 执行动作，修改path dfs(input,step+1 or gap--,result); 恢复path } }
DFS和回溯法的区别
回溯法=DFS+剪枝
DFS和递归的区别
递归和迭代是对应的。
DFS可以用递归实现，也可用栈实现
递归一般总是用来实现DFS
递归有两种加速策略：（1）剪枝：对中间结果进行判断，提前返回（2）缓存：缓存中间结果，防止重复计算，用空间换时间
