一、口诀
广列深归，分分贪动回
二、含义
广度优先一般使用队列实现，深度优先一般使用递归实现。
分治法，分支定界法，贪婪算法，动态规划，回溯法
分治法：一分为二
贪婪算法：不断尝试
动态规划：递归不重复
回溯法：深度优先
分支定界：广度优先
三、分治法
分而治之方法与软件设计的模块化方法非常相似。为了解决一个大的问题，可以：
1）把它分成两个或多个更小的问题
2）分别解决每个小问题
3）把各个小问题的解答组合起来，即可得到原问题的解答。
小问题通常与原问题相似，可以递归地使用分而治之策略来解决。
应用：残缺棋盘、排序、选择和一个计算几何问题--找出二维空间中距离最近的两个点。
四、贪婪算法
贪婪算法采用逐步构造最优解的方法，在每个阶段，都作出一个看上去最优的决策。决策一旦作出，就不可再更改，作出贪婪决策的依据称为贪婪准则。
应用：货箱装船、背包、拓扑排序、二分覆盖问题。最短路径问题、最小代价生成树。
五、动态规划
动态规划是建立在最优原则的基础上，采用动态规划方法，可以优雅而高效地解决许多用贪婪算法或分而治之算法无法解决的问题。
和贪婪算法一样，在动态规划中，可将一个问题的解决方案视为一系列决策的结果。不同的是，在贪婪算法中，每采用一次贪婪准则便做出一个不可撤回的
决策，而在动态规划中，还要考察每个最优决策序列中是否包含一个最优子序列。
应用：背包、图像压缩、矩阵乘法链、最短路径问题、无交叉子集和元件折叠。
1951年美国数学家R.Bellman等人，根据一类多阶段问题的特点，把多阶段决策问题变换为一系列互相联系的单阶段问题，然后逐个加以解决。一些静态
模型，只要人为地引进“时间”因素，分成时段，就可以转化成多阶段的动态模型，用动态规划方法去处理。与此同时，他提出了解决这类问题的“最优化原理”（Principle of optimality）：
“一个过程的最优决策具有这样的性质：即无论其初始状态和初始决策如何，其今后诸策略对以第一个决策所形成的状态作为初始状态的过程而言，必须构成最优策略”。简言之，一个最优策略的子策略，对于它的初态和终态而言也必是最优的。
这个“最优化原理”如果用数学化一点的语言来描述的话，就是：假设为了解决某一优化问题，需要依次作出n个决策D1，D2，…，Dn，如若这个决策序列是最优的，对于任何一个整数k，1 < k < n，不论前面k个决策是怎样的，以后的最优决策只取决于由前面决策所确定的当前状态，即以后的决策Dk+1，Dk+2，…，Dn也是最优的。
最优化原理是动态规划的基础。任何一个问题，如果失去了这个最优化原理的支持，就不可能用动态规划方法计算。能采用动态规划求解的问题都需要满足一定的条件：
（1）问题中的状态必须满足最优化原理；
（2）问题中的状态必须满足无后效性。
所谓的无后效性是指：“下一时刻的状态只与当前状态有关，而和当前状态之前的状态无关，当前的状态是对以往决策的总结”。
问题求解模式
动态规划所处理的问题是一个多阶段决策问题，一般由初始状态开始，通过对中间阶段决策的选择，达到结束状态。这些决策形成了一个决策序列，同时确定了完成整个过程的一条活动路线（通常是求最优的活动路线）。如图所示。动态规划的设计都有着一定的模式，一般要经历以下几个步骤：
初始状态→│决策1│→│决策2│→…→│决策ｎ│→结束状态
（1）划分阶段：按照问题的时间或空间特征，把问题分为若干个阶段。在划分阶段时，注意划分后的阶段一定要是有序的或者是可排序的，否则问题就无法求解。
（2）确定状态和状态变量：将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示出来。当然，状态的选择要满足无后效性。
（3）确定决策并写出状态转移方程：因为决策和状态转移有着天然的联系，状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。所以如果确定了决策，状态转移方程也就可写出。但事实上常常是反过来做，根据相邻两段各状态之间的关系来确定决策。
（4）寻找边界条件：给出的状态转移方程是一个递推式，需要一个递推的终止条件或边界条件。
动态规划算法的有效性依赖于待求解问题本身具有的两个重要性质：最优子结构性质和子问题重叠性质。
（1）最优子结构性质。如果问题的最优解所包含的子问题的解也是最优的，我们就称该问题具有最优子结构性质（即满足最优化原理）。最优子结构性质为动态规划算法解决问题提供了重要线索。
（2）子问题重叠性质。子问题重叠性质是指在用递归算法自顶向下对问题进行求解时，每次产生的子问题并不总是新问题，有些子问题会被重复计算多次。动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只计算一次，然后将其计算结果保存在一个表格中，当再次需要计算已经计算过的子问题时，只是在表格中简单地查看一下结果，从而获得较高的解题效率。
六、回溯法
对候选解进行系统检查的方法有多种，其中回溯和分支定界法是比较常用的两种方法。按照这两种方法对候选解进行系统检查通常会使问题的求解时间大大减少。
应用：这两种算法可以被用来设计货箱装船、背包、最大完备子图、旅行商和电路板排列问题的求解算法。
回溯是一种系统地搜索问题解答的方法，为了实现回溯，首先需要为问题定义一个解空间，这个空间必须至少包含问题的一个解，下一步是组织解空间以便它能被容易地
搜索，典型的组织方法是图或树。
七、分支定界法
分支定界法是另一种搜索解空间的方法，与回溯法不同的是，回溯算法使用深度优先方法搜索树结构，而分支定界一般用宽度优先或最小耗费方法来搜索这些树。
它与回溯的主要区别在于对E-节点的扩充方式。有两种常用的方法可以用来选择下一个E-节点：
1）先进先出（FIFO） 即从活节点表中取出节点的顺序与加入节点的顺序相同，因此活节点表的性质与队列相同。
2）最小耗费或最大收益法 在这种模式中，每个节点都有一个对应的耗费或收益。如果查找一个具有最小耗费的解，则活节点表可用最小堆来建立，下一个E-节点就是
具有最小耗费的活节点，反之，使用最大堆来建立。
八、总结
动态规划算法是以上几种算法中难度最大的一种，需要好好参详。
其他算法如其名，比较容易理解。