一、算法内容
1.简介
深度优先搜索DFS（Depth First Search）按照深度优先的方式进行搜索，可以理解为“一条路走到黑”地
穷举所有可行的方案，并不断尝试，直到找到一种情况满足问题问题的要求。那么这个方案就是一个问
题的解。
2.递归与回溯
深度优先搜索可以用递归实现，而且几乎都是用递归实现，所以要学会深度优先搜索，首先必须要学会
递归。但切忌将递归与深度优先搜索混为一谈。深度优先搜索和递归的区别是：深度优先搜索是一种算
法，注重的是思想；而递归是一种基于编程语言的实现方式。
深度优先搜索最重要地就是回溯，它的作用是将状态恢复到上一级。你可以想象小时候玩迷宫游戏的行
为，选择某一些路径进行尝试，如果不行就倒回来走其他的地方，这样倒回去的操作就是回溯。只有不
断地尝试，不断地回溯才是一个完整的深度优先搜索。
如果将搜索的过程画出来，那么它就像一棵树，每一个结点都有相应的状态，分别代表了一种可能性。
之所以叫做深度优先，是因为我们总是走到树的叶子处才开始返回，在树上就是先往深的地方走。
3.剪枝
在我们搜索的时候，理论上我们需要把所有的情况都考虑到，但是实际上，有一些情况我们不需要走到
尽头就知道这是不合理的。就像走到树上的某一个位置之后，我们知道接下来无论走到哪里都不可能得
到正确的答案了，那么就可以直接返回，相当于剪掉了搜索树上的一根树枝。
