DFS即Depth First Search，是一种用于遍历或搜索树或图的算法。
沿着树的深度遍历树的节点，尽可能深的搜索树的分支。其过程简要来说是对每一个可能的分支路径深入到不能再深入为止，而且每个节点只能访问一次。
dfs算法剪枝分类
1、顺序性剪枝
若一些题的搜索顺序对答案无影响，那么搜索顺序的不同会导致搜索树形态的改变，优先搜索分支较少的阶段，此时能减少搜索的规模。
2、重复性剪枝
在搜索的时候如果有多种方式可以到达一个状态，那么我们只需要搜索一个分支就可以了。
3、可行性剪枝
可行性剪枝是对搜索正确性的一个保证，当分支在递归边界的时候回溯。
4、最优性剪枝
在搜索过程中，如果当前阶段的代价已经超过我们已知的最小代价，那么此时继续搜索下去就失去了意义。
5、记忆化剪枝
记录搜索状态的结果，当重复遍历一个状态的时候就可以直接返回这个状态的答案，避免重复的搜索。
DFS其实叫深度优先搜索算法，起始它只是一种搜索的方法思路，并没有固定的算法格式。
作为搜索算法的一种，DFS对于寻找一个解的NP（包括NPC）问题作用很大。但是，搜索算法毕竟是时间复杂度是O(n!)的阶乘级算法，它的效率非常低，在数据规模变大时，这种算法就显得力不从心了。
DFS思路：
DFS思路是一条路走到底，撞到了墙再回头。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被访问为止，属于盲目搜索。
深度优先搜索算法(Depth-First-Search) :是一种用于遍历或搜索树或图的算法。 沿着树的深度遍历树的节点，尽可能深的搜索树的分支。当节点v的所在边都己被探寻过或者在搜寻时结点不满足条件，搜索将回溯到发现节点v的那条边的起始节点。整个进程反复进行直到所有节点都被访问为止。
话说大诗人李白，一生好饮。幸好他从不开车。
一天，他提着酒壶，从家里出来，酒壶中有酒2斗。他边走边唱：
无事街上走，提壶去打酒。
逢店加一倍，遇花喝一斗。
这一路上，他一共遇到店5次，遇到花10次，已知最后一次遇到的是花，他正好把酒喝光了。
请你计算李白遇到店和花的次序，可以把遇店记为a，遇花记为b。则：babaabbabbabbbb 就是合理的次序。像这样的答案一共有多少呢？请你计算出所有可能方案的个数（包含题目给出的）。
注意：通过浏览器提交答案。答案是个整数。不要书写任何多余的内容。
答案：14
小明刚刚看完电影《第39级台阶》，离开电影院的时候，他数了数礼堂前的台阶数，恰好是39级!
站在台阶前，他突然又想着一个问题：
如果我每一步只能迈上1个或2个台阶。先迈左脚，然后左右交替，最后一步是迈右脚，也就是说一共要走偶数步。那么，上完39级台阶，有多少种不同的上法呢？
请你利用计算机的优势，帮助小明寻找答案。
要求提交的是一个整数。
注意：不要提交解答过程，或其它的辅助说明文字。
欢迎分享，转载请注明来源：民族网
