****# Basic Exhaustive Search - 基础穷竭搜索
穷竭搜索是将所有的可能性罗列出来，在其中寻找答案的方法。主要有深度优先搜索和广度优先搜索这两种方法。
在一个函数中再次调用该函数自身的行为叫做递归，这样的函数被称为递归函数。
在实现递归函数时，一定要注意递归的深度，防止栈溢出。
斐波那契数列：
public static int fib(int n) {
if(n <= 1) return n;
else return fib(n-1) + fib(n-2);
}先总结一下写一个递归函数的心得：
- 出口条件，即递归“什么时候结束”，这个通常在递归函数的开始就写好；
- 初始条件，也就是这个递归调用以什么样的初始条件开始；
- 如何由”情况 n” 变化到”情况 n+1″, 也就是非出口情况，也就是一般情况——”正在”递归中的情况；
栈是一种LIFO（Last In First Out，即后进先出）的数据结构，支持push和pop两种数据操作的数据结构。push在栈顶放入数据，pop则从栈顶取出数据。
函数调用的过程是通过使用栈实现的，因此，递归函数的递归过程也可以改用栈上的操作来实现。下面是JDK提供的栈的集合示例。
JDK栈操作示例：
public static void main(String[] args) {
Deque<Integer> stack = new ArrayDeque<>(); // 注意栈的构造
stack.push(1);
stack.push(2);
stack.push(3);
while (!stack.isEmpty()) {
if (stack.peek() % 2 == 0) System.out.print("=>");
System.out.println(stack.pop());
}
}队列（Queue）与栈一样支持push(offer)和pop(poll)两个操作，但与栈不同的是，pop完成的不是取出最顶端的元素，而是取出最低端的元素。也就是说最初放入的元素能够最先被取出，这种行为被叫做FIFO（First In First Out，即先进先出）。
JDK队列操作示例：
public static void main(String[] args) {
Queue<Integer> queue = new LinkedList<>();
queue.offer(1);
queue.offer(2);
queue.offer(3);
while (!queue.isEmpty()) {
if (queue.peek() % 2 == 0) System.out.print("=>");
System.out.println(queue.poll());
}
}深度优先搜索（DFS，Depth-First Search）是搜索的手段之一。它从某个状态开始，不断地转移状态直到无法转移，然后回退到前一步的状态，继续转移到其他状态，如此不断重复，直至找到最终的解。
核心思想：从一个顶点V0开始，沿着一条路一直走到底，如果发现不能到达目标解，那就返回到上一个节点，然后从另一条路开始走到底，这种尽量往深处走的概念即是深度优先的概念。
DFS适合此类题目：给定初始状态跟目标状态，要求判断从初始状态到目标状态是否有解。
PKU： 1088 - 滑雪 1176 1321 1416 1564 1753 2492 3083 3411
与深度优先搜索的不同之处在于搜索的顺序，宽度优先搜索总是先搜索距离初始状态近的状态。也就是说，它是按照开始状态→只需1次转移就可以到达的所有状态→只需2次转移就可以到达的所有状态→……这样的顺序进行搜索。对于同一个状态，宽度优先搜索只经过一次，因此复杂度为O(状态数×转移的方式)。
深度优先搜索（隐式地）利用了栈进行计算，而宽度优先搜索则利用了队列。搜索时首先将初始状态添加到队列里，此后从队列的最前端不断取出状态，把从该状态可以转移到的状态中尚未访问过的部分加入队列，如此往复，直至队列被取空或找到了问题的解。通过观察这个队列，我们可以就知道所有的状态都是按照距初始状态由近及远的顺序被遍历的。
BFS适合此类题目：给定初始状态跟目标状态，要求从初始状态到目标状态的最短路径。
PKU：1136 1249 1028 1191 3278 1426 3126 3087 3414
广度优先搜索的缺点：在树的层次较深&子节点数较多的情况下，消耗内存十分严重。广度优先搜索适用于节点的子节点数量不多，并且树的层次不会太深的情况。
那么深度优先就可以克服这个缺点，因为每次搜的过程，每一层只需维护一个节点。但回过头想想，广度优先能够找到最短路径，那深度优先能否找到呢？深度优先的方法是一条路走到黑，那显然无法知道这条路是不是最短的，所以你还得继续走别的路去判断是否是最短路？
于是深度优先搜索的缺点也出来了：难以寻找最优解，仅仅只能寻找有解。其优点就是内存消耗小，克服了刚刚说的广度优先搜索的缺点。
所谓剪枝，顾名思义，就是通过某种判断，避免一些不必要的遍历过程，形象的说，就是剪去了搜索树中的某些“枝条”，故称剪枝。应用剪枝优化的核心问题是设计剪枝判断方法，即确定哪些枝条应当舍弃，哪些枝条应当保留的方法。
// TODO OJ题目