五大经典算法（贪婪、动态规划、分治、回溯、分支限界法）及其联系和比较

一、贪心法

贪心算法的含义：

贪心算法（也叫贪婪算法）是指在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，只做出在某种意义上的局部最优解。贪心算法不是对所有问题都能得到全局最优解，得到的是局部最优解，关键是贪心策略的选择，不同的贪婪策略会导致得到差异非常大的结果。选择的贪心策略必须具备无后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。

一般步骤：

1. 建立数学模型来描述问题；
2. 把求解的问题分成若干个子问题；
3. 对每一子问题求解，得到子问题的局部最优解；
4. 把子问题的局部最优解合成原来问题的一个解。

经典问题：

贪心法是动态规划法的特例，如0-1背包，钱币找零问题，最小代价生成树（prim算法和cruskal算法），huffman算法，以及Dijkstra算法。

二、动态规划

基本思想：

动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值的解。

动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的（即下一个子阶段的求解是建立在上一个子阶段的解的基础上，进行进一步的求解）。若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，节省时间。

我们可以用一个表来记录所有已解的子问题的答案。 不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。这就是动态规划法的基本思路。具体的动态规划算法多种多样，但它们具有相同的填表格式。

应用场景：

适用动态规划的问题必须满足最优化原理、无后效性和重叠性。

1. 最优化原理（最优子结构性质）
   最优化原理可这样阐述：一个最优化策略具有这样的性质，不论过去状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。简而言之，一个最优化策略的子策略总是最优的。一个问题满足最优化原理又称其具有最优子结构性质。如果可以把局部子问题的解结合起来得到全局最优解，那这个问题就具备最优子结构。

2. 无后效性
   将各阶段按照一定的次序排列好之后，对于某个给定的阶段状态，它以前各阶段的状态无法直接影响它未来的决策，而只能通过当前的这个状态。换句话说，每个状态都是过去历史的一个完整总结。这就是无后向性，又称为无后效性。即要求每个子问题的决策不能对后面其他未解决的问题产影响， 如果产生就无法保证决策的最优性。

3. 子问题的重叠性
   如果计算最优解时需要处理很多相同的问题，那么这个问题就具备重复子问题。
   动态规划必须保证我们分割成的子问题也能按照相同的方法分割成更小的子问题， 并这些自问题的最终分割情况是可以解决的。
   动态规划将原来具有指数级时间复杂度的搜索算法改进成了具有多项式时间复杂度的算法。其中的关键在于解决冗余，这是动态规划算法的根本目的。动态规划实质上是一种以空间换时间的技术，它在实现的过程中，不得不存储产生过程中的各种状态，所以它的空间复杂度要大于其它的算法。

动态规划算法的核心就是提供了一个memory来缓存重复子问题的结果，避免了递归的过程中的大量的重复计算。动态规划算法的难点在于怎么将问题转化为能够利用动态规划算法来解决。当重复子问题的数目比较小时，动态规划的效果也会很差。如果问题存在大量的重复子问题的话，那么动态规划对于效率的提高是非常恐怖的。

一般步骤：

1. 分析最优解的性质，并刻画其结构特征。
2. 递归地定义最优值。
3. 以自底向上的方式或自顶向下的记忆化方法（备忘录法）计算出最优值。
4. 根据计算最优值时得到的信息，构造一个最优解。

步骤(1)–(3)是动态规划算法的基本步骤。在只需要求出最优值的情形，步骤(4)可以省略，若需要求出问题的一个最优解，则必须执行步骤(4)。此时，在步骤(3)中计算最优值时，通常需记录更多的信息，以便在步骤(4)中，根据所记录的信息，快速地构造出一个最优解。

在实际的做题中也可以这样去做：

1. 确定子问题： 在这一步重点是分析那些变量是随着问题规模的变小而变小的， 那些变量与问题的规模无关。
2. 确定状态：根据上面找到的子问题来给你分割的子问题限定状态。
3. 推导出状态转移方程：这里要注意你的状态转移方程是不是满足所有的条件， 注意不要遗漏。
4. 确定边界条件：先根据题目的限制条件来确定题目中给出的边界条件是否能直接推导出， 如果不行也可以尝试从边界条件反推（举个例子：a(n)→a(2)有递推关系， 但是a(2)→a(1)不符合上述递推关系， 我们就可以考虑用a(1)来倒推出a(2)， 然后将递推的终点设置为a(2)）;
5. 确定实现方式：这个依照个人习惯，就像是01背包的两层for循环的顺序。
6. 确定优化方法：很多时候你会发现走到这里步的时候你需要返回第1步重来。首先考虑降维问题（优化内存）， 优先队列、四边形不等式（优化时间）等等。

常用方法：

1. 模型匹配法：熟练记忆并且理解LIS、LCS、01背包、完全背包、区间模型、树状模型。基本就是将原模型加以变化后加以套用
2. 三要素法：
   1）先确定阶段：如数塔问题， 先确定当前选的是第几层。
   2）先确定状态：这是最常用的绝大多数的DP都是这么做的。
   3）先确定决策：背包问题（选还是不选第i种物品）
3. 寻找规律法：从小的状态开始推， 耐心找规律， 或者可以在本地暴力打表， 暴力出奇迹。
4. 边界条件法： 一般边界时容易导出状态关系的地方。
5. 增加约束条件法

经典问题：

如多段图问题，备忘录方法，求全路径最短路径的Floyd弗洛伊德算法，最长公共子序列，斐波那契数列问题。

三、分治法

分治法的含义：

分治算法的基本思想是将一个规模为N的问题分解为K个规模较小的子问题，这些子问题相互独立且与原问题性质相同。 求出子问题的解，就可得到原问题的解。

运用分治策略解决的问题一般来说具有以下特点：

1. 原问题可以分解为多个子问题。这些子问题与原问题相比，只是问题的规模有所降低，其结构和求解方法与原问题相同或相似。
2. 原问题在分解过程中，递归地求解子问题。由于递归都必须有一个终止条件，因此，当分解后的子问题规模足够小时，应能够直接求解。
3. 在求解并得到各个子问题的解后应能够采用某种方式、方法合并或构造出原问题的解。

不难发现，在分治策略中，由于子问题与原问题在结构和解法上的相似性，用分治方法解决的问题，大都采用了递归的形式。在各种排序方法中，如归并排序、堆排序、快速排序等，都存在有分治的思想。

一般步骤：

1. 分解，将要解决的问题划分成若干规模较小的同类问题；
2. 求解，当子问题划分得足够小时，用较简单的方法解决；
3. 合并，按原问题的要求，将子问题的解逐层合并构成原问题的解。

经典问题：

归并排序、堆排序、快速排序、二分查找、全排列问题、整数划分问题、求第k大元素。

四、回溯法

回溯法的含义：

回溯法（探索与回溯法）是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。

回溯法就是对隐式图的深度优先搜索算法。 回溯法在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。算法搜索至解空间树的任意一点时，先判断该结点是否包含问题的解。如果肯定不包含（剪枝过程），则跳过对该结点为根的子树的搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略搜索。

回溯法为了避免生成那些不可能产生最佳解的问题状态，要不断地利用限界函数(bounding function)来处死(剪枝)那些实际上不可能产生所需解的活结点，以减少问题的计算量。具有限界函数的深度优先生成法称为回溯法。（回溯法 = 穷举 + 剪枝）

两个常用的剪枝函数：

• 约束函数：在扩展结点处减去不满足约束的子数
• 限界函数：减去得不到最优解的子树

用回溯法解题的一个显著特征是在搜索过程中动态产生问题的解空间。在任何时刻，算法只保存从根结点到当前扩展结点的路径。如果解空间树中从根结点到叶结点的最长路径的长度为h(n)，则回溯法所需的计算空间通常为O(h(n))。而显式地存储整个解空间则需要O(2^h(n))或O(h(n)!)内存空间。

一般步骤：

1. 针对所给问题，定义问题的解空间；
2. 确定易于搜索的解空间结构；
3. 以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。

经典问题：

如n皇后，图的着色问题、求子集、字符串的排列等问题。

五、分支限界法

基本思想：

分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。

分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。

在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。 此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。

分支限界法的搜索策略：

在当前节点（扩展节点）处，先生成其所有的儿子节点（分支），然后再从当前的活节点（当前节点的子节点）表中选择下一个扩展节点。为了有效地选择下一个扩展节点，加速搜索的进程，在每一个活节点处，计算一个函数值（限界），并根据函数值，从当前活节点表中选择一个最有利的节点作为扩展节点，使搜索朝着解空间上有最优解的分支推进，以便尽快地找出一个最优解。分支限界法解决了大量离散最优化的问题。

一般步骤：

1. 定义问题的解空间
2. 确定解空间的结构
3. 以广度优先方式搜索整个解空间
4. 找出所要的解（限界函数的使用）

常见的两种分支限界法：

1. 队列式(FIFO)分支限界法
   队列式分支限界法将活节点表组织成一个队列，并将队列的先进先出原则选取下一个节点为当前扩展节点。
2. 优先队列式分支限界法
   优先队列式分支限界法将活节点表组织成一个优先队列，并将优先队列中规定的节点优先级选取优先级最高的下一个节点成为当前扩展节点。如果选择这种选择方式，往往将数据排成最大堆或者最小堆来实现。

经典问题：

01背包，最大团，单源最短路径，装载问题，布线问题。
可参考：分支限界法总结–例题(01背包，最大团，单源最短路径，装载问题，布线问题)

六、总结

动态规划和分治的区别和联系：

动态规划算法与分治法的相同点在于，都是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。
动态规划与分治法的不同点在于，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的，而分治法的子问题相互独立且与原问题性质相同。

分支限界法与回溯法的区别：

（1）求解目标：回溯法的求解目标是遍历整个解空间，找出解空间树中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。
（2）搜索方式的不同：回溯法以深度优先的方式搜索解空间树，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树。

贪婪、动态规划、回溯的区别和联系：

首先，这些方法所要解决的问题，一般都是决策问题。而贪心法一般是来求解最优问题的，而且他们其实都是在对问题的状态空间树进行搜索，在这个状态空间树中搜索最佳的路径以便求出最优策略。而贪心法是从上到下只进行深度搜索的，也就是说它是一口气走到黑的，一口气吃成胖子的，它的代价取决于子问题的数目，也就是树的高度，每次在当前问题的状态上作出的选择都是1，也就是说，它其实是不进行广度搜索的，这也造成了它的一个缺点：它得出的解不一定是最优解，很有可能是近似最优解。

而动态规划法在最优子结构的前提下，从状态空间树的叶子节点开始向上进行搜索，并且在每一步都根据叶子节点的当前问题的状况作出选择，从而作出最优决策，它的代价就是子问题的个数和可选择的数目，所以它求出的解一定是最优解。

回溯法是从上到下进行深度搜索，如果深度搜索没有进行到底而不满足决策函数了，那么再回去从最近的可以岔开的地方选择另一条路，继续之前的深度搜索，如果搜索到底，那么再通过for循环进行广度搜索。所以它也是深度搜索和广度搜索并行的。求出的解也一定是最优解。

最优解问题大部分都可以拆分成一个个的子问题，把解空间的遍历视作对子问题树的遍历，则以某种形式对树整个的遍历一遍就可以求出最优解，大部分情况下这是不可行的。贪心算法和动态规划本质上是对子问题树的一种修剪，两种算法要求问题都具有的一个性质就是子问题最优性(组成最优解的每一个子问题的解，对于这个子问题本身肯定也是最优的)。动态规划方法代表了这一类问题的一般解法，我们自底向上构造子问题的解，对每一个子树的根，求出下面每一个叶子的值，并且以其中的最优值作为自身的值，其它的值舍弃。而贪心算法是动态规划方法的一个特例，可以证明每一个子树的根的值不取决于下面叶子的值，而只取决于当前问题的状况。换句话说，不需要知道一个节点所有子树的情况，就可以求出这个节点的值。由于贪心算法的这个特性，它对解空间树的遍历不需要自底向上，而只需要自根开始，选择最优的路，一直走到底就可以了。

最后，五大算法都有相通的地方，理解透彻还是要靠实战。五大算法是开发、算法类岗位应聘时手撕代码的常考题，尤其是动态规划和回溯，把LeetCode上经典题目都做一遍，基本就能理解个差不多了。

参考网址：
浅谈动态规划法与贪心法和回溯法的联系
五大常用算法之三：贪心算法
最常用的五大算法
五大经典算法
动态规划(1)：基本思路以及步骤
动态规划算法的基本步骤
分支限界法
分支限界法
五大常用算法——分支限界算法详解及经典例题