DFS(深搜)算法

深度优先搜索算法(Depth-First-Search) :是一种用于遍历或搜索树或图的算法。 沿着树的深度遍历树的节点，尽可能深的搜索树的分支。当节点v的所在边都己被探寻过或者在搜寻时结点不满足条件，搜索将回溯到发现节点v的那条边的起始节点。整个进程反复进行直到所有节点都被访问为止。

话说大诗人李白，一生好饮。幸好他从不开车。

一天，他提着酒壶，从家里出来，酒壶中有酒2斗。他边走边唱：

无事街上走，提壶去打酒。

逢店加一倍，遇花喝一斗。

这一路上，他一共遇到店5次，遇到花10次，已知最后一次遇到的是花，他正好把酒喝光了。

请你计算李白遇到店和花的次序，可以把遇店记为a，遇花记为b。则：babaabbabbabbbb 就是合理的次销念早序。像这样的答案一共有多少呢？请你计算出所有可能方案的亏雀个数（包含题目给出的）。

注意：通过浏览器提交答案。答案是个整数。不要书写任何多余的内容。

答案：14

小明刚刚看完电影《第39级台阶》，离开高铅电影院的时候，他数了数礼堂前的台阶数，恰好是39级!

站在台阶前，他突然又想着一个问题：

如果我每一步只能迈上1个或2个台阶。先迈左脚，然后左右交替，最后一步是迈右脚，也就是说一共要走偶数步。那么，上完39级台阶，有多少种不同的上法呢？

请你利用计算机的优势，帮助小明寻找答案。

要求提交的是一个整数。

注意：不要提交解答过程，或其它的辅助说明文字。

深度优先搜索是一种在开发爬虫早期使用较多的方法。它的目的是要达到被搜索结构的叶结点(即那些不包含任何超链的HTML文件) 。在一个HTML文件中，当一个超链被选择后，被链接的HTML文件将执行深度优先搜索，即在搜索其余的超链结果之前必须先完整地搜索单独的一条链。深度优先搜索沿着HTML文件上的超链走到不能再深入为止，然后返回到某一个HTML文件，再继续选择该HTML文件中的其他超链。当不再有其他超链可选择时，说明搜索已经结束.事实上,深度优先搜索属于图算法的一种,英文缩写为DFS即Depth First Search.其过程简要来说是对每一个可能的分支路径深入到不能再深入为止,而且每个节点只能访问一次. 在我们遇到的一些问题当中，有些问题我们不能够确切的找出数学模型，即找不出一种直接求解的方法，解决这一类问题，我们一般采用搜索的方法解决。搜索就是用问题的所有可能去试探，按照一定的顺序、规则，不断去试探，直到找到问题的解，试完了也没有找到解，那就是无解，试探时一定要试探完所有的情况（实际上就是穷举）； 对于问题的第一个状态，叫初始状态，要求的状态叫目标状态。 搜索就是把规则应用于实始状态，在其产生的状态中，直到得到一个目标状态为止。 产生新的状态的过程叫扩展（由一个状态，应用规则，产生新状态的过程） 搜索的要点：（1）初始状态； （2）重复产生新状态； （3）检查新状态是否为目标，是结束，否转（2）； 如果搜索是以接近起始状态的程序依次扩展状态的，叫宽度优先搜索。 如果扩展是首先扩展新产生的状态，则叫深度优先搜索。 深度优先搜索 深度优先搜索用一个数组存放产生的所有状态。 （1） 把初始状态放入数组中，设为当前状态； （2） 扩展当前的状态，产生一个新的状态放入数组中，同时把新产生的状态设为当前状态； （3） 判断当前状态是否和前面的重复，如果重复则回到上一个状态，产生它的另一状态； （4） 判断当前状态是否为目标状态，如果是目标，则找到一个解答，结束算法。 （5） 如果数组为空，说明无解。 对于pascal语言来讲，它支持递归，在递归时可以自动实现回溯（利用局部变量）所以使用递归编写深度优先搜索程序相对简单，当然也有非递颂仔陵归实现的算法。 搜索是人工智能中的一种基本方法，是一项非常普遍使用的算法策略，能够解决许许多多的常见问题，在某些情况下我们很难想到高效的戚尘解法时，搜索往往是可选的唯一选择。按照标准的话来讲：搜索算法是利用计算机的高性能来有目的的穷野戚举一个问题的部分或所有的可能情况，从而求出问题的解的一种方法。 搜索虽然简单易学易于理解，但要掌握好并写出速度快效率高优化好的程序却又相当困难，总而言之，搜索算法灵活多变，一般的框架很容易写出，但合适的优化却要根据实际情况来确定。在搜索算法中，深度优先搜索（也可以称为回溯法）是搜索算法里最简单也最常见的，今天我们就从这里讲起，下面的内容假设读者已经知道最基本的程序设计和简单的递归算法。 这是我找的资料，希望能帮到你~~

---