算法，广义地讲就是解决问题的方法和过程。可以使用自然语言、伪代码、流程图等多种不同的方法来描述。如果把一个程序比喻成一个具有生命的人，那么数据结构就是这个人的躯体，而算法则是这个人的灵魂。

枚举

枚举法，又称穷举法，或称为暴力破解法，是一种针对于密码的破译方法，即将密码进行逐个推算直到找出真正的密码为止。

基本思想：在可能的解空间中穷举出每一种可能的解，并对每一个可能解进行判断，从中得到问题的答案。虽然枚举法本质上属于搜索策略，但是它与后面讲的回溯法或宽度优先搜索有所不同。总的来说，枚举就是通过列举所有的可能性进行一一判断检查。

适用条件：

1、可预先确定每个状态的元素个数n。

2、可预先确定每个状态元素a1,a2,…,an的值域。

注意事项：使用枚举思想解决实际问题，最关键的步骤是划定问题的解空间，并在该解空间中一一枚举每一个可能的解。这里有两点需要注意。一是解空间的划定必须保证覆盖问题的全部解。如果解空间集合用H表示，问题的解集用h表示，那么只有当时，才能使用枚举法求解。二是解空间集合及问题的解集一定是离散的集合，也就是说集合中的元素是可列的、有限的。

常见类型：枚举排列、枚举子集。

常见方法： 递归地枚举，这种方法往往更为直观；递推（循环）地枚举，这种方法往往写起来更为简洁。

主要优点：由于枚举算法一般是现实问题的“直译”，且是建立在考察大量状态、甚至是穷举所有状态的基础之上的，因此比较直观，易于理解，其算法的正确性也比较容易证明。

主要缺点：枚举算法的效率取决于枚举状态的数量以及单个状态枚举的代价，因此效率比较低。在某些情况下，我们可以通过利用题目的特点去除相当大的一部分情况的列举，从而提高枚举的效率。

算法优化：

1、    提取有效信息;

2、    减少重复计算;

3、    将原问题化为更小的问题;

4、    根据问题的性质进行截枝;

5、    引进其他算法。

递推

递推法是一种重要的数学方法，在数学的各个领域中都有广泛的运用，也是计算机用于数值计算的一个重要算法。这种算法特点是：一个问题的求解需一系列的计算，在已知条件和所求问题之间总存在着某种相互联系的关系，在计算时，如果可以找到前后过程之间的数量关系（即递推式），那么，从问题出发逐步推到已知条件，此种方法叫逆推。无论顺推还是逆推，其关键是要找到递推式。这种处理问题的方法能使复杂运算化为若干步重复的简单运算，充分发挥出计算机擅长于重复处理的特点。

  递推算法的首要问题是得到相邻的数据项间的关系（即递推关系）。递推算法避开了求通项公式的麻烦，把一个复杂的问题的求解，分解成了连续的若干步简单运算。一般说来，可以将递推算法看成是一种特殊的迭代算法。

基本思想：递推是按照一定的规律来计算序列中的每个项，通常是通过计算机前面的一些项来得出序列中的指定项的值。把一个复杂的庞大的计算过程转化为简单过程的多次重复，该算法利用了计算机速度快和不知疲倦的机器特点。

主要步骤：建立递推关系式；确定边界条件；递推求解。

应用分类：一般递推问题；组合计数类问题；一类博弈问题的求解；动态规划问题的递推关系。

动态规划与递推的关系

1、一般递推边界条件很明显，动态规划边界条件比较隐蔽，容易被忽视；

2、一般递推数学性较强，动态规划数学性相对较弱；

3、一般递推不划分阶段，动态规划一般有较为明显的阶段。

五种典型的递推关系

1、Fibonacci数列

在所有的递推关系中，Fibonacci数列应该是最为大家所熟悉的。在最基础的程序设计语言Logo语言中，就有很多这类的题目。而在较为复杂的Basic、Pascal、C语言中，Fibonacci数列类的题目因为解法相对容易一些，逐渐退出了竞赛的舞台。可是这不等于说Fibonacci数列没有研究价值，恰恰相反，一些此类的题目还是能给我们一定的启发的。

Fibonacci数列的代表问题是由意大利著名数学家Fibonacci于1202年提出的“兔子繁殖问题”(又称“Fibonacci问题”)。

问题的提出：有雌雄一对兔子，假定过两个月便可繁殖雌雄各一的一对小兔子。问过n个月后共有多少对兔子？

解：设满x个月共有兔子Fx对，其中当月新生的兔子数目为Nx对。第x-1个月留下的兔子数目设为Fx-1对。则：

F_x=N_x+F_x-1

N_x=F_x-2  (即第x-2个月的所有兔子到第x个月都有繁殖能力了)

∴F_x=F_x-1+F_x-2  边界条件：F0=0，F1=1

由上面的递推关系可依次得到

F₂=F₁+F₀=1，F₃=F₂+F₁=2，F₄=F₃+F₂=3，F₅=F₄+F₃=5，……。

Fabonacci数列常出现在比较简单的组合计数问题中，例如以前的竞赛中出现的“骨牌覆盖”问题。在优选法中，Fibonacci数列的用处也得到了较好的体现。

2、Hanoi塔问题

问题的提出：Hanoi塔由n个大小不同的圆盘和三根木柱a,b,c组成。开始时，这n个圆盘由大到小依次套在a柱上，如图所示。

要求把a柱上n个圆盘按下述规则移到c柱上：

1、一次只能移一个圆盘；

2、圆盘只能在三个柱上存放；

3、在移动过程中，不允许大盘压小盘。

问将这n个盘子从a柱移动到c柱上，总计需要移动多少个盘次？

解：设hn为n个盘子从a柱移到c柱所需移动的盘次。显然，当n=1时，只需把a 柱上的盘子直接移动到c柱就可以了，故h1=1。当n=2时，先将a柱上面的小盘子移动到b柱上去；然后将大盘子从a柱移到c 柱；最后，将b柱上的小盘子移到c柱上，共记3个盘次，故h2=3。以此类推，当a柱上有n(n2)个盘子时，总是先借助c柱把上面的n-1个盘子移动到b柱上，然后把a柱最下面的盘子移动到c柱上；再借助a柱把b柱上的n-1个盘子移动到c柱上；总共移动h_n-1+1+h_n-1个盘次。

∴h_n=2h_n-1+1    边界条件：h₁=1

3、平面分割问题

问题的提出：设有n条封闭曲线画在平面上，而任何两条封闭曲线恰好相交于两点，且任何三条封闭曲线不相交于同一点，问这些封闭曲线把平面分割成的区域个数。

解：设a_n为n条封闭曲线把平面分割成的区域个数。由图3-13可以看出：a₂-a₁=2；a₃-a₂=4；a₄-a₃=6。

从这些式子中可以看出a_n-a_n-1=2(n-1)。当然，上面的式子只是我们通过观察4幅图后得出的结论，它的正确性尚不能保证。下面不妨让我们来试着证明一下。当平面上已有n-1条曲线将平面分割成a_n-1­个区域后，第n-1条曲线每与曲线相交一次，就会增加一个区域，因为平面上已有了n-1条封闭曲线，且第n条曲线与已有的每一条闭曲线恰好相交于两点，且不会与任两条曲线交于同一点，故平面上一共增加2(n-1)个区域，加上已有的an-1个区域，一共有a_n-1+2(n-1)个区域。所以本题的递推关系是a_n=a_n-1+2(n-1)，边界条件是a₁=1。

4、Catalan数

Catalan数首先是由Euler在精确计算对凸n边形的不同的对角三角形剖分的个数问题时得到的，它经常出现在组合计数问题中。

问题的提出：在一个凸n边形中，通过不相交于n边形内部的对角线，把n边形拆分成若干三角形，不同的拆分数目用h_n表示，h_n即为Catalan数。例如五边形有如下五种拆分方案，故h₅=5。求对于一个任意的凸n边形相应的h_n。

Catalan数是比较复杂的递推关系，尤其在竞赛的时候，选手很难在较短的时间里建立起正确的递推关系。当然，Catalan数类的问题也可以用搜索的方法来完成，但是，搜索的方法与利用递推关系的方法比较起来，不仅效率低，编程复杂度也陡然提高。

5、第二类Stirling数

在五类典型的递推关系中，第二类Stirling是最不为大家所熟悉的。也正因为如此，我们有必要先解释一下什么是第二类Strling数。

定义：n个有区别的球放到m个相同的盒子中，要求无一空盒，其不同的方案数用S(n,m)表示，称为第二类Stirling数。

下面就让我们根据定义来推导带两个参数的递推关系——第二类Stirling数。

解：设有n个不同的球，分别用b1,b2,……bn表示。从中取出一个球bn，bn的放法有以下两种：

1、bn独自占一个盒子；那么剩下的球只能放在m-1个盒子中，方案数为S2(n-1,m-1)；

2、bn与别的球共占一个盒子；那么可以事先将b1,b2,……bn-1这n-1个球放入m个盒子中，然后再将球bn可以放入其中一个盒子中，方案数为mS2(n-1,m)。

综合以上两种情况，可以得出第二类Stirling数定理：

S2(n,m)=mS2(n-1,m)+S2(n-1,m-1)   (n>1,m1)

边界条件可以由定义2推导出：

S2(n,0)=0；S2(n,1)=1；S2(n,n)=1；S2(n,k)=0(k>n)。     

小结：通过上面对五种典型的递推关系建立过程的探讨，可知对待递推类的题目，要具体情况具体分析，通过找到某状态与其前面状态的联系，建立相应的递推关系。

递归

一个函数、过程、概念或数学结构，如果在其定义或说明内部又直接或间接地出现有其本身的引用，则称它们是递归的或者是递归定义的。在程序设计中，过程或函数直接或者间接调用自己，就被称为递归调用。其中直接调用自己称为直接递归，而将A调用B，B以调用A的递归叫做间接递归。

基本思想：

1、递归是借助于一个递归工作栈来实现。递归=递推+回归。

2、递推：问题向一极推进, 这一过程叫做递推。这一过程相当于压栈。

3、回归：问题逐一解决，最后回到原问题，这一过程叫做回归。这一过程相当于弹栈。

注意事项：

1、    递归就是在过程或函数里调用自身；

2、    在使用递归策略时，必须有一个明确的递归结束条件，称为递归出口。

主要优点：采用递归方法编写的问题解决程序具有结构清晰，可读性强等优点，且递归算法的设计比非递归算法的设计往往要容易一些，所以当问题本身是递归定义的，或者问题所涉及到的数据结构是递归定义的，或者是问题的解决方法是递归形式的时候，往往采用递归算法来解决。

主要缺点：执行的效率很低，尤其在边界条件设置不当的情况下，极有可能陷入死循环或者内存溢出的窘境。递归实现的代价是巨大的栈空间的耗费，那是因为过程每向前递推一次，程序将本层的实在变量（值参和变参）、局部变量构成一个“工作记录”压入工作栈的栈顶，只有退出该层递归时，才将这一工作记录从栈顶弹出释放部分空间。由此可以想到，减少每个“工作记录”的大小便可节省部分空间。例如某些变参可以转换为全局变量，某些值参可以省略以及过程内部的精简。

应用分类：

1、递归的定义问题。树结构是由递归定义的。因此，在解决与树有关的问题时，常常可以采用递归的方法。

2、解决搜索问题。因为搜索产生的节点成树状结构，所以可以用递归方法解决。这类例子很多，如“N皇后”问题，全排列，哈密顿回路，图的可着色性等搜索问题。

3、实现分治思想。不难发现，在各种时间复杂度为nlogn排序方法中，大都采用了递归的形式。因为无论是分治合并排序，还是堆排序、快速排序，都存在有分治的思想。只要分开处理，就可以采用递归。其实进行分治，也是一个建树的过程。

4、用于输出动态规划的中间过程。动态规划对空间要求较高，若要保存中间过程用于输出，则可能要增加一倍的空间需求。此时，如果采用递归输出，就完全不需要浪费这宝贵的空间。

递归调用过程，实质上是不断调用过程或函数的过程，由于递归调用一次，所有子程序的变量（局部变量、变参等）、地址在计算机内部都有用特殊的管理方法——栈（先进后出）来管理，一旦递归调用结束，计算机便开始根据栈中存储的地址返回各子程序变量的值，并进行相应操作。

	递归	递推
适合解决的问题	1. 问题本身是递归定义的，或者问题所涉及到的数据结构是递归定义的，或者是问题的解决方法是递归形式的 2. 需要利用分治思想解决的问题 3. 回溯、深度优先搜索 4. 输出动态规划的中间过程	1. 能够用递推式计算的数学题 2. 动态规划（必须使用递推或记忆化搜索）
特点	结构清晰、可读性强 目的性强	速度较快、比较灵活 思路不易想到
编码方式	在函数中调用自己	迭代（使用for循环等）
替代方法	问题的性质不同，改写的方法也不同。 ① 有的问题可以根据程序本身的特点，使用栈来模拟递归调用。 ② 有的问题可以改写成递推或迭代算法。	在拓扑关系不明显时，可以采用记忆化搜索。

搜索

搜索，某种意义上就是对于枚举算法的一种改进，通过在枚举的过程中，不断排除一些不可能达到的情况，从而达到优化复杂度的效果。

常见方法：

1、深度优先搜索（DFS）

主要思想：从一个顶点沿一条路一直走，如果发现到不了目标节点，则返回上一个节点，沿另一条路一直走到底。总体来说，DFS就是一个一个一直处理到底，发现无法得到结果之后，逐步返回寻求其它的出路。

算法优化：

1、最优化剪枝：求最优值时，当前的状态无论如何不可能比最优值更优，则退出，可与展望结合剪枝；

2、可行性剪枝：提前判断该状态是否能得到可行解，如不能则退出；

3、记忆化搜索：对于已经搜索过的状态直接退出；

4、改变搜索顺序：对于看起来希望更大的决策先进行搜索；

5、优化搜索策略；

6、预处理找到大体搜索翻译；

7、改写成IDA*算法。

2、宽度优先搜索（BFS）

主要思想：首先访问起始节点的所有邻接点，然后再访问较远的区域，逐步扩大范围，直到找到了目标节点。BFS是一个处理不含边权的图当中求解最短路径的一个非常有效的方法。这一算法也是很多重要的图的算法的原型。Dijkstra单源最短路径算法和Prim最小生成树算法都采用了和宽度优先搜索类似的思想。

注意事项：

1、每生成一个子结点，就要提供指向它们父亲结点的指针。当解出现时候，通过逆向跟踪，找到从根结点到目标结点的一条路径。当然不要求输出路径，就没必要记父亲。

2、生成的结点要与前面所有已经产生结点比较，以免出现重复结点，浪费时间和空间，还有可能陷入死循环。

3、如果目标结点的深度与“费用”（如：路径长度）成正比，那么，找到的第一个解即为最优解，这时，搜索速度比深度搜索要快些，在求最优解时往往采用宽度优先搜索；如果结点的“费用”不与深度成正比时，第一次找到的解不一定是最优解。

4、宽度优先搜索的效率还有赖于目标结点所在位置情况，如果目标结点深度处于较深层时，需搜索的结点数基本上以指数增长。

算法优化：

1、判重的优化：hash，二叉排序树；

2、双向广搜或启发式搜索；

3、改写成A*算法；

4、二分优化。

	DFS	BFS
优势	1. 比较适合回溯类搜索 2. 参数传递、状态修改和恢复都比较方便 3. 自顶向下地处理问题 4. 记忆化搜索容易实现 5. 能很快到达解答树的底端	1. 解决“最少步数”、“深度最小”问题 2. 问题的解靠近解答树的根结点 3. 启发式搜索在BFS中更容易实现 4. 能立刻停止搜索
缺点	1. 使用递归算法容易导致栈溢出 2. 有时不容易输出方案 3. 不易立即结束搜索	1. 空间一般比DFS大 2. 状态重复的排除有时耗时多

3、迭代加深搜索

深度优先搜索的优点在于能较高效地逼近解，缺点在于初始递归方向错误会带来很严重后果；宽度优先搜索的优点在于能迅速找到答案不算大的解，缺点在于解答案较大时所耗时间与空间都比较大。于是，在综合以上两个算法之后，出现了一个折中的方法：迭代加深搜索。

主要思想：通过限定下界k，然后允许深度优先搜索搜索k层，一旦仍没有找到有效解，则增大下界。

主要优点：相对于深度优先搜索并没有大很多的时间开销，但能部分解决深度优先搜索的局限；无需宽度优先搜索一般的大空间需求。

分治

基本思想：将一个较大规模的问题分成多个（一般是2个）较小规模的互相独立且与原问题相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。当我们将问题分解成两个较小问题求解时的分治方法称之为二分法。

适用条件：

1、该问题的规模缩小到一定的程度就可以容易地解决；

2、该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质；

3、利用该问题分解出的子问题的解可以合并为该问题的解；

4、该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子子问题。

递归与分治的算法思想往往是相伴而生的，它们在各类算法中使用非常频繁，应用递归和分治的算法思想有时可以设计出代码简洁且比较高效的算法来。

解题步骤：

1、分解，将要解决的问题划分成若干规模较小的同类问题；

2、求解，当子问题划分得足够小时，用较简单的方法解决；

3、合并，按原问题的要求，将子问题的解逐层合并构成原问题的解。

应用分类： 二分搜索；大整数乘法；Strassen矩阵乘法；棋盘覆盖；合并排序；快速排序；线性时间选择；最接近点对问题；循环赛日程表；汉诺塔等。

贪心

基本思想：贪心，又称贪婪算法。指的是在对问题求解过程中，总是做出目前来看最优的选择，也就是说贪心算法不会考虑全局最优解，而只会不断考虑局部最优解。是一种对某些求最优解问题的更简单、更迅速的设计技术。往往可以以较低的代码复杂度与时间复杂度而得到较优的结果，对于求解近似值的作用很大。

贪心算法没有固定的算法框架，算法设计的关键是贪心策略的选择。必须注意的是，贪心算法不是对所有问题都能得到整体最优解，选择的贪心策略必须具备无后效性，即某个状态以后的过程不会影响以前的状态，只与当前状态有关。

当存在一些题目的正解想不出来，并且一个贪心原则又效果不好的情况下，可以采取多个贪心原则同时用，并取最优的方案来解决。但对于相当一部分需要求解最优值的问题，实际上我们会发现我们通常可以采用动态规划或者网络流的方法取代贪心算法。

适用条件：

1、可通过局部的贪心选择来达到问题的全局最优解。运用贪心策略解题，一般来说需要一步步的进行多次的贪心选择。在经过一次贪心选择之后，原问题将变成一个相似的，但规模更小的问题，而后的每一步都是当前看似最佳的选择，且每一个选择都仅做一次。

2、原问题的最优解包含子问题的最优解，即问题具有最优子结构的性质。在下面示例的背包问题中，第一次选择单位重量价值最大的货物，它是第一个子问题的最优解，第二次选择剩下的货物中单位重量价值最大的货物，同样是第二个子问题的最优解，依次类推。

3、其次，如何选择一个贪心标准？正确的贪心标准可以得到问题的最优解，在确定采用贪心策略解决问题时，不能随意的判断贪心标准是否正确，尤其不要被表面上看似正确的贪心标准所迷惑。在得出贪心标准之后应给予严格的数学证明。

解题步骤：

1、建立数学模型来描述问题；

2、把求解的问题分成若干个子问题；

3、对每一子问题求解，得到子问题的局部最优解；

4、把子问题的解局部最优解合成原来解问题的一个解。

 回溯

基本思想：在包含问题的所有解的解空间树中，按照深度优先搜索的策略，从根结点出发深度探索解空间树。当探索到某一结点时，要先判断该结点是否包含问题的解，如果包含，就从该结点出发继续探索下去；如果该结点不包含问题的解，那就说明以该结点为根结点的子树一定不包含问题的最终解，因此要跳过对以该结点为根的子树的系统探索，逐层向其祖先结点回溯。这个过程叫做解空间树的“剪枝”操作。如果应用回溯法求解问题的所有解，要回溯到解空间树的树根，这样根结点的所有子树都被探索到才结束。如果只要求解问题的一个解，那么在探索解空间树时，只要搜索到问题的一个解就可以结束了。

动态规划

基本思想：在多阶段决策的问题中，各个阶段采取的决策，一般来说是与时间或空间有关的。决策依赖于当前状态，又随即引起状态的转移，一个决策序列就是在变化的状态中产生出来，故有“动态”的含义，我们称这种解决多阶段决策最优化的过程为动态规划方法。

基本概念：

阶段：把所求问题的过程按照时间或空间恰当地分成若干个相互联系的阶段。

状态：表示每个阶段的客观状态，它既是某阶段的出发位置，又是前一阶段的终点。

无后效性：如果给定某一阶段的状态，则在这一阶段以后过程的发展不受这阶段以前各段状态的影响，所以各阶段确定时，整个过程也就确定了。

决策：一个阶段的状态给定以后，从该状态演变到下一阶段状态的一种选择(行动)。

策略：由每个阶段的决策组成的序列。

最优性原理：把一个大问题划分成多个子问题，对于整个问题必须最优的情况时，问题也必须最优，即问题具备最优子结构的性质。

适用条件：

1、最优子结构。如果问题的一个最优解中包含了子问题的最优解，则该问题具有最优子结构。也称最优化原理。最优子结构也可以理解为“整体最优则局部最优”。反之不一定成立。

2、重叠子问题。在解决整个问题时，要先解决其子问题，要解决这些子问题，又要先解决他们的子子问题 ……。而这些子子问题又不是相互独立的，有很多是重复的，这些重复的子子问题称为重叠子问题。动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只解一次，而后将其解保存在一个表中，以后再遇到这些相同问题时直接查表就可以，而不需要再重复计算，每次查表的时间为常数。

3、无后效性原则。已经求得的状态，不受未求状态的影响。

解题步骤：

1、判断问题是否具有最优子结构性质，若不具备，则不能用动态规划；

2、把问题分成若干个子问题(分阶段)；

3、建立状态转移方程(递推公式)；

4、找出边界条件；

5、设定初始值；

6、递推求解。

状态转移方程的构造是动态规划过程中最重要的一步，也是最难的一步。对于大多数的动态规划，寻找状态转移方程有一条十分高效的通道，就是寻找变化中的不变量（已经求得的值）。

PS:第九讲树与二叉树自测题参考答案

1D 2B 3D 4E 5C 6B 7A 8C 9AC 10BCE 11E 12B 

13 n0=nk*(k-1)+1     

14 n1+n2+……=nm

设总共有n个节点 显然就有n＝n0+n1+n2+...+nm 其中no就表示叶子节点

而除了根节点外每个节点都由别的结点引出n-1=0*n0+1*n1+2*n2+...+m*nm

联立两个等式得n0=1+n2+2n3+...+(m-1)nm

非终端节点就是非叶子节点了也就是

n1+n2+n3+...+nm