四种基本的算法思想：贪心算法、分治算法、回溯算法、动态规划；它们应该是算法思想，并不是具体的算法，常用来指导我们设计具体的算法和编码等。
四者区别：

• 贪心、回溯、动态规划可以归为一类，可以抽象成多阶段决策最优解模型。
• 分治单独可以作为一类，分治算法解决的问题尽管大部分也是最优解问题，但是，大部分都不能抽象成多阶段决策模型。

回溯算法是个“万金油”。基本上能用的动态规划、贪心解决的问题，都可以用回溯算法解决。回溯算法相当于穷举搜索。穷举所有的情况，然后对比得到最优解。不过，回溯算法的时间复杂度非常高，是指数级别的，只能用来解决小规模数据的问题。对于大规模数据的问题，用回溯算法解决的执行效率就很低了。
动态规划比回溯算法高效，但是并不是所有问题都可以用动态规划来解决。能用动态规划解决的问题，需要满足三个特征，最优子结构、无后效性和重复子问题。在重复子问题这一点上，动态规划和分治算法的区分非常明显。分治算法要求分割成的子问题，不能有重复子问题，而动态规划正好相反，动态规划之所以高效，就是因为回溯算法实现中存在大量的重复子问题。
贪心算法实际上是动态规划算法的一种特殊情况。它解决问题起来更加高效，代码实现也更简洁。不过，它可以解决的问题也更加有限，它能解决的问题需要满足三个条件，最优子结构、无后效性和贪心选择性（这里不怎么强调重复子问题）。“贪心选择性”的意思是，通过局部最优的选择，能产生全局的最优选择。每一个阶段，都选择当前看起来最优的决策，所有阶段的决策完成之后，最终由这些局部最优解构成全局最优解。

贪心算法greedy algorithm

概念

贪心算法有很多经典的应用，比如霍夫曼编码（Huffman Coding）、Prim 和 Kruskal 最小生成树算法、还有 Dijkstra 单源最短路径算法。
实际上，用贪心算法解决问题的思路，并不总能给出最优解。
举例：在一个有权图中，我们从顶点 S 开始，找一条到顶点 T 的最短路径（路径中边的权值和最小）。贪心算法的解决思路是，每次都选择一条跟当前顶点相连的权最小的边，直到找到顶点 T。按照这种思路，求出的最短路径是 S->A->E->T，路径长度是 1+4+4=9。但是，这种贪心的选择方式，最终求的路径并不是最短路径，因为路径 S->B->D->T 才是最短路径，因为这条路径的长度是 2+2+2=6。

贪心算法不工作的主要原因是，前面的选择，会影响后面的选择。第一步选择最优的走法（边最短），但有可能因为这一步选择，导致后面每一步的选择都很糟糕，最终也就无缘全局最优解了。
贪心算法解决问题的步骤：
第一步，当看到这类问题的时候，首先要联想到贪心算法：针对一组数据，定义了限制值和期望值，希望从中选出几个数据，在满足限制值的情况下，期望值最大。
第二步，尝试看下这个问题是否可以用贪心算法解决：每次选择当前情况下，在对限制值同等贡献量的情况下，对期望值贡献最大的数据。
第三步，举几个例子看下贪心算法产生的结果是否是最优的。大部分情况下，举几个例子验证一下就可以了。严格地证明贪心算法的正确性，是非常复杂的，需要涉及比较多的数学推理。而且，从实践的角度来说，大部分能用贪心算法解决的问题，贪心算法的正确性都是显而易见的，也不需要严格的数学推导证明。

应用举例

贪心算法适用的场景比较有限。这种算法思想更多的是指导设计基础算法。比如最小生成树算法、单源最短路径算法，这些算法都用到了贪心算法。不要刻意去记忆贪心算法的原理，多练习才是最有效的学习方法。

1. 分糖果

有 m 个糖果和 n 个孩子。现在要把糖果分给这些孩子吃，但是糖果少，孩子多（m可以把这个问题抽象成，从 n 个孩子中，抽取一部分孩子分配糖果，让满足的孩子的个数（期望值）是最大的。这个问题的限制值就是糖果个数 m。
对于一个孩子来说，如果小的糖果可以满足，就没必要用更大的糖果，这样更大的就可以留给其他对糖果大小需求更大的孩子。另一方面，对糖果大小需求小的孩子更容易被满足，可以从需求小的孩子开始分配糖果。因为满足一个需求大的孩子跟满足一个需求小的孩子，对期望值的贡献是一样的。每次从剩下的孩子中，找出对糖果大小需求最小的，然后发给他剩下的糖果中能满足他的最小的糖果，这样得到的分配方案，也就是满足的孩子个数最多的方案。

2. 钱币找零

假设有 1 元、2 元、5 元、10 元、20 元、50 元、100 元这些面额的纸币，它们的张数分别是 c1、c2、c5、c10、c20、c50、c100。现在要用这些钱来支付 K 元，最少要用多少张纸币呢？
在生活中肯定是先用面值最大的来支付，如果不够，就继续用更小一点面值的，以此类推，最后剩下的用 1 元来补齐。
在贡献相同期望值（纸币数目）的情况下，希望多贡献点金额，这样就可以让纸币数更少，这就是一种贪心算法的解决思路。

3. 区间覆盖

假设有 n 个区间，区间的起始端点和结束端点分别是 [l1, r1]，[l2, r2]，[l3, r3]，……，[ln, rn]。从这 n 个区间中选出一部分区间，这部分区间满足两两不相交（端点相交的情况不算相交），最多能选出多少个区间？

这个处理思想在很多贪心算法问题中都有用到，比如任务调度、教师排课等等问题。
解决思路：假设这 n 个区间中最左端点是 lmin，最右端点是 rmax。这个问题就相当于，选择几个不相交的区间，从左到右将 [lmin, rmax] 覆盖上。
按照起始端点从小到大的顺序对这 n 个区间排序。每次选择的时候，左端点跟前面的已经覆盖的区间不重合的，右端点又尽量小的，这样可以让剩下的未覆盖区间尽可能的大，就可以放置更多的区间。这实际上就是一种贪心的选择方法。

4. 霍夫曼编码

假设有一个包含 1000 个字符的文件，每个字符占 1 个 byte（1byte=8bits），存储这 1000 个字符就一共需要 8000bits，如何节省空间？利用贪心算法来实现对数据压缩编码，有效节省数据存储空间的。
普通方式：假设通过统计分析发现，这 1000 个字符中只包含 6 种不同字符，假设它们分别是 a、b、c、d、e、f。而 3 个二进制位（bit）就可以表示 8 个不同的字符，所以，为了尽量减少存储空间，每个字符用 3 个二进制位来表示。那存储这 1000 个字符只需要 3000bits 就可以了，比原来的存储方式节省了很多空间。不过，还有没有更加节省空间的存储方式呢？
霍夫曼编码：霍夫曼编码是一种十分有效的编码方法，广泛用于数据压缩中，其压缩率通常在 20%～90% 之间。
霍夫曼编码不仅会考察文本中有多少个不同字符，还会考察每个字符出现的频率，根据频率的不同，选择不同长度的编码。霍夫曼编码试图用这种不等长的编码方法，来进一步增加压缩的效率。如何给不同频率的字符选择不同长度的编码呢？根据贪心的思想，可以把出现频率比较多的字符，用稍微短一些的编码；出现频率比较少的字符，用稍微长一些的编码。
对于等长的编码来说，解压缩起来很简单。比如用 3 个 bit 表示一个字符。在解压缩的时候，每次从文本中读取 3 位二进制码，然后翻译成对应的字符。但是，霍夫曼编码是不等长的，每次应该读取 1 位还是 2 位、3 位等等来解压缩呢？这个问题就导致霍夫曼编码解压缩起来比较复杂。为了避免解压缩过程中的歧义，霍夫曼编码要求各个字符的编码之间，不会出现某个编码是另一个编码前缀的情况。

假设这 6 个字符出现的频率从高到低依次是 a、b、c、d、e、f。任何一个字符的编码都不是另一个的前缀，在解压缩的时候，每次会读取尽可能长的可解压的二进制串，所以在解压缩的时候也不会歧义。经过这种编码压缩之后，这 1000 个字符只需要 2100bits 就可以了。

霍夫曼编码的思想并不难理解，但是如何根据字符出现频率的不同，给不同的字符进行不同长度的编码呢？这里的处理稍微有些技巧。
把每个字符看作一个节点，并且辅带着把频率放到优先级队列中。从队列中取出频率最小的两个节点 A、B，然后新建一个节点 C，把频率设置为两个节点的频率之和，并把这个新节点 C 作为节点 A、B 的父节点。最后再把 C 节点放入到优先级队列中。重复这个过程，直到队列中没有数据。

现在，给每一条边加上画一个权值，指向左子节点的边我们统统标记为 0，指向右子节点的边，统统标记为 1，那从根节点到叶节点的路径就是叶节点对应字符的霍夫曼编码。

回溯算法back tracking

概念

贪心算法并不一定能得到最优解。那有没有什么办法能得到最优解呢？
回溯的处理思想，有点类似枚举搜索；枚举所有的解，找到满足期望的解。为了有规律地枚举所有可能的解，避免遗漏和重复，把问题求解的过程分为多个阶段。每个阶段，先随意选一条路走，当发现这条路走不通的时候（不符合期望的解），就回退到上一个岔路口，另选一种走法继续走。回溯算法非常适合用递归代码实现。在实现的过程中，剪枝操作是提高回溯效率的一种技巧。利用剪枝，并不需要穷举搜索所有的情况，从而提高搜索效率。

应用举例

回溯算法可以解决很多问题，比如：深度优先搜索算法、八皇后、0-1 背包、正则表达式匹配、数独、图的着色、旅行商问题、全排列、编译原理中的语法分析….

八皇后

有一个 8x8 的棋盘，希望往里放 8 个棋子（皇后），每个棋子所在的行、列、对角线都不能有另一个棋子。你可以看我画的图，第一幅图是满足条件的一种方法，第二幅图是不满足条件的。八皇后问题就是期望找到所有满足这种要求的放棋子方式。

把这个问题划分成 8 个阶段，依次将 8 个棋子放到第一行、第二行、第三行……第八行。在放置的过程中，不停地检查当前的方法，是否满足要求。如果满足，则跳到下一行继续放置棋子；如果不满足，那就再换一种方法，继续尝试。

0-1 背包

0-1 背包这个问题的经典解法是动态规划，不过还有一种简单但没有那么高效的解法，就是回溯算法。
0-1 背包问题有很多变体，比较基础的如下：有一个背包，背包总的承载重量是 Wkg。现在有 n 个物品，每个物品的重量不等，并且不可分割。现在期望选择几件物品，装载到背包中。在不超过背包所能装载重量的前提下，如何让背包中物品的总重量最大？
背包问题要么装要么不装，所以叫 0-1 背包问题。显然这个问题已经无法通过贪心算法来解决。
对于每个物品来说，都有两种选择，装进背包或者不装进背包。对于 n 个物品来说，总的装法就有 2n 种，去掉总重量超过 Wkg 的，从剩下的装法中选择总重量最接近 Wkg 的。不过，如何才能不重复地穷举出这 2n 种装法呢？
这里就可以用回溯的方法。可以把物品依次排列，整个问题就分解为了 n 个阶段，每个阶段对应一个物品怎么选择。先对第一个物品进行处理，选择装进去或者不装进去，然后再递归地处理剩下的物品。还稍微用到了一点搜索剪枝的技巧，当发现已经选择的物品的重量超过 Wkg 之后，就停止继续探测剩下的物品。

正则表达式

正则表达式中，最重要的就是通配符，通配符结合在一起，可以表达非常丰富的语义。假设正表达式中只包含“”和“?”这两种通配符，并对这两个通配符的语义稍微做改变，其中，“”匹配任意多个（大于等于 0 个）任意字符，“?”匹配零个或者一个任意字符。如何用回溯算法，判断一个给定的文本，能否跟给定的正则表达式匹配？
依次考察正则表达式中的每个字符，当是非通配符时，就直接跟文本的字符进行匹配，如果相同，则继续往下处理；如果不同，则回溯。
如果遇到特殊字符的时候，就有多种处理方式了，也就是所谓的岔路口，比如“*”有多种匹配方案，可以匹配任意个文本串中的字符，就先随意的选择一种匹配方案，然后继续考察剩下的字符。如果中途发现无法继续匹配下去了，就回到这个岔路口，重新选择一种匹配方案，然后再继续匹配剩下的字符。

动态规划Dynamic Programming

概念

什么样的问题适合用动态规划来解决呢？或者说动态规划能解决的问题有什么规律可循呢？实际上，动态规划作为一个非常成熟的算法思想，这部分理论被总结为““一个模型三个特征”。

“一个模型”

指的是动态规划适合解决的问题的模型，这个模型定义为“多阶段决策最优解模型”。一般是用动态规划来解决最优问题。而解决问题的过程，需要经历多个决策阶段。每个决策阶段都对应着一组状态。然后寻找一组决策序列，经过这组决策序列，能够产生最终期望求解的最优值。
“三个特征”？分别是最优子结构、无后效性和重复子问题。

1. 最优子结构

最优子结构指的是，问题的最优解包含子问题的最优解。反过来说就是，可以通过子问题的最优解，推导出问题的最优解。如果把最优子结构，对应到模型上，即后面阶段的状态可以通过前面阶段的状态推导出来。

2. 无后效性

无后效性有两层含义，第一层含义是，在推导后面阶段的状态的时候，只关心前面阶段的状态值，不关心这个状态是怎么一步一步推导出来的。第二层含义是，某阶段状态一旦确定，就不受之后阶段的决策影响。无后效性是一个非常“宽松”的要求。只要满足前面提到的动态规划问题模型，其实基本上都会满足无后效性。

3. 重复子问题

不同的决策序列，到达某个相同的阶段时，可能会产生重复的状态。

大部分动态规划能解决的问题，都可以通过回溯算法来解决，只不过回溯算法解决起来效率比较低，时间复杂度是指数级的。动态规划比较适合用来求解最优问题，比如求最大值、最小值等等。它可以非常显著地降低时间复杂度，提高代码的执行效率。

解决思路

动态规划解题的一般思路，有两种思路。分别叫作，状态转移表法和状态转移方程法。

1. 状态转移表法

一般能用动态规划解决的问题，都可以使用回溯算法的暴力搜索解决。所以当拿到问题的时候，可以先用简单的回溯算法解决，然后定义状态，每个状态表示一个节点，然后对应画出递归树。从递归树中，很容易可以看出来，是否存在重复子问题，以及重复子问题是如何产生的。以此来寻找规律，看是否能用动态规划解决。
找到重复子问题之后，接下来有两种处理思路，第一种是直接用回溯加“备忘录”的方法，来避免重复子问题。从执行效率上来讲，这跟动态规划的解决思路没有差别。第二种是使用动态规划的解决方法，状态转移表法。
先画出一个状态表。状态表一般都是二维数组。其中，每个状态包含三个变量，行、列、数组值。根据决策的先后过程，从前往后，根据递推关系，分阶段填充状态表中的每个状态。最后将这个递推填表的过程，翻译成代码，就是动态规划代码了。
尽管大部分状态表都是二维的，但是如果问题的状态比较复杂，需要很多变量来表示，那对应的状态表可能就是高维的，比如三维、四维。这时就不适合用状态转移表法来解决了。一方面是因为高维状态转移表不好画图表示，另一方面是因为人脑确实很不擅长思考高维的东西。

2. 状态转移方程法

状态转移方程法类似递归的解题思路。需要分析某个问题如何通过子问题来递归求解，也就是所谓的最优子结构。根据最优子结构，写出递归公式，也就是所谓的状态转移方程。一般情况下，有两种代码实现方法，一种是递归加“备忘录”，另一种是迭代递推。
状态转移方程是解决动态规划的关键。如果能写出状态转移方程，那动态规划问题基本上就解决一大半了。但是很多动态规划问题的状态本身就不好定义，状态转移方程也就更不好想到。

应用举例

“一个模型三个特征”实例剖析

假设有一个 n 乘以 n 的矩阵 w[n][n]。矩阵存储的都是正整数。棋子起始位置在左上角，终止位置在右下角。将棋子从左上角移动到右下角。每次只能向右或者向下移动一位。从左上角到右下角，会有很多不同的路径可以走。把每条路径经过的数字加起来看作路径的长度。那从左上角移动到右下角的最短路径长度是多少呢？

首先，从 (0, 0) 走到 (n-1, n-1)，总共要走 2(n-1) 步，也就对应着 2(n-1) 个阶段。每个阶段都有向右走或者向下走两种决策，并且每个阶段都会对应一个状态集合。把状态定义为 min_dist(i, j)，其中 i 表示行，j 表示列。min_dist 表达式的值表示从 (0, 0) 到达 (i, j) 的最短路径长度。所以，这个问题是一个多阶段决策最优解问题，符合动态规划的模型。

其次，可以用回溯算法来解决这个问题，画一下递归树，就会发现，递归树中有重复的节点。说明这个问题中存在重复子问题。

如果走到 (i, j) 这个位置，我能通过 (i-1, j)，(i, j-1) 这两个位置移动过来，也就是说，想要计算 (i, j) 位置对应的状态，只需要关心 (i-1, j)，(i, j-1) 两个位置对应的状态，并不关心棋子是通过什么样的路线到达这两个位置的。而且，仅仅允许往下和往右移动，不允许后退，所以，前面阶段的状态确定之后，不会被后面阶段的决策所改变，所以这个问题符合“无后效性”这一特征。
刚刚定义状态的时候，把从起始位置 (0, 0) 到 (i, j) 的最小路径，记作 min_dist(i, j)。因为只能往右或往下移动，所以只能从 (i, j-1) 或者 (i-1, j) 两个位置到达 (i, j)。也就是说，到达 (i, j) 的最短路径要么经过 (i, j-1)，要么经过 (i-1, j)，而且到达 (i, j) 的最短路径肯定包含到达这两个位置的最短路径之一。换句话说就是，min_dist(i, j) 可以通过 min_dist(i, j-1) 和 min_dist(i-1, j) 两个状态推导出来。这个问题符合“最优子结构”。

0-1 背包问题

回溯的解决方法，就是穷举搜索所有可能的装法，然后找出满足条件的最大值。不过，回溯算法的复杂度比较高，是指数级别的。
动态规划求解：把整个求解过程分为 n 个阶段，每个阶段会决策一个物品是否放到背包中。每个物品决策完之后，背包中的物品的重量会有多种情况，也就是说，会达到多种不同的状态，对应到递归树中，就是有很多不同的节点。把每一层重复的状态（节点）合并，只记录不同的状态，然后基于上一层的状态集合，来推导下一层的状态集合。可以通过合并每一层重复的状态，这样就保证每一层不同状态的个数都不会超过 w 个（w 表示背包的承载重量）。于是就成功避免了每层状态个数的指数级增长。
用一个二维数组 states[n][w+1]，来记录每层可以达到的不同状态。第 0 个物品的重量是 2，要么装入背包，要么不装入背包，决策完之后，会对应背包的两种状态，背包中物品的总重量是 0 或者 2。用 states[0][0]=true 和 states[0][2]=true 来表示这两种状态。第 1 个物品的重量也是 2，基于之前的背包状态，在这个物品决策完之后，不同的状态有 3 个，背包中物品总重量分别是 0(0+0)，2(0+2 or 2+0)，4(2+2)。用 states[1][0]=true，states[1][2]=true，states[1][4]=true 来表示这三种状态。
以此类推，直到考察完所有的物品后，整个 states 状态数组就都计算好了。只需要在最后一层，找一个值为 true 的最接近 w（这里是 9）的值，就是背包中物品总重量的最大值。

用回溯算法解决这个问题的时间复杂度 O(2n)，是指数级的。动态规划的时间复杂度是O(n*w)。n 表示物品个数，w 表示背包可以承载的总重量。
尽管动态规划的执行效率比较高，但是需要额外申请一个 n 乘以 w+1 的二维数组，对空间的消耗比较多。所以，动态规划是一种空间换时间的解决思路。你可能要问了，有什么办法可以降低空间消耗吗？实际上，只需要一个大小为 w+1 的一维数组就可以解决这个问题。动态规划状态转移的过程，都可以基于这个一维数组来操作。

分治算法divide and conquer

概念

分治算法（divide and conquer）的核心思想其实就是四个字，分而治之 ，也就是将原问题划分成 n 个规模较小，并且结构与原问题相似的子问题，递归地解决这些子问题，然后再合并其结果，就得到原问题的解。
分治算法是一种处理问题的思想，递归是一种编程技巧。实际上，分治算法一般都比较适合用递归来实现。分治算法的递归实现中，每一层递归都会涉及这样三个操作：

• 分解：将原问题分解成一系列子问题；
• 解决：递归地求解各个子问题，若子问题足够小，则直接求解；
• 合并：将子问题的结果合并成原问题。

分治算法能解决的问题，一般需要满足下面这几个条件：

• 原问题与分解成的小问题具有相同的模式；
• 原问题分解成的子问题可以独立求解，子问题之间没有相关性，这一点是分治算法跟动态规划的明显区别；
• 具有分解终止条件，也就是说，当问题足够小时，可以直接求解；
• 可以将子问题合并成原问题，而这个合并操作的复杂度不能太高，否则就起不到减小算法总体复杂度的效果了。

  应用举例

  分治算法思想的应用是非常广泛的，并不仅限于指导编程和算法设计（比如快排、归并排序）。它还经常用在海量数据处理的场景中。

  处理大数据

  如果要处理的数据量非常大，没法一次性放到内存中，这个时候，这些数据结构和算法（快排、归并）就无法工作了。比如给 10GB 的订单文件按照金额排序这样一个需求，但是因为数据量大，机器的内存可能只有 2、3GB 这样子，无法一次性加载到内存，也就无法通过单纯地使用快排、归并等基础算法来解决。
  要解决这种数据量大到内存装不下的问题，就可以利用分治的思想。可以将海量的数据集合根据某种方法，划分为几个小的数据集合，每个小的数据集合单独加载到内存来解决，然后再将小数据集合合并成大数据集合。实际上，利用这种分治的处理思路，不仅仅能克服内存的限制，还能利用多线程或者多机处理，加快处理的速度。
  给 10GB 的订单排序，就可以先扫描一遍订单，根据订单的金额，将 10GB 的文件划分为几个金额区间。比如订单金额为 1 到 100 元的放到一个小文件，101 到 200 之间的放到另一个文件，以此类推。这样每个小文件都可以单独加载到内存排序，最后将这些有序的小文件合并，就是最终有序的 10GB 订单数据了。
  如果订单数据存储在类似 GFS 这样的分布式系统上，当 10GB 的订单被划分成多个小文件的时候，每个文件可以并行加载到多台机器上处理，最后再将结果合并在一起，这样并行处理的速度也加快了很多。不过有一个点要注意，就是数据的存储与计算所在的机器是同一个或者在网络中靠的很近（比如一个局域网内，数据存取速度很快），否则就会因为数据访问的速度，导致整个处理过程不但不会变快，反而有可能变慢。

  MapReduce

  MapReduce 是 Google 大数据处理的三驾马车之一，另外两个是 GFS 和 Bigtable。它在倒排索引、PageRank 计算、网页分析等搜索引擎相关的技术中都有大量的应用。
  而对于谷歌搜索引擎来说，网页爬取、清洗、分析、分词、计算权重、倒排索引等等各个环节中，都会面对如此海量的数据（比如网页）。所以，利用集群并行处理显然是大势所趋。实际上，MapReduce 框架只是一个任务调度器，底层依赖 GFS 来存储数据，依赖 Borg 管理机器。它从 GFS 中拿数据，交给 Borg 中的机器执行，并且时刻监控机器执行的进度，一旦出现机器宕机、进度卡壳等，就重新从 Borg 中调度一台机器执行。
  尽管 MapReduce 的模型非常简单，但是在 Google 内部应用非常广泛。它除了可以用来处理这种数据与数据之间存在关系的任务，比如 MapReduce 的经典例子，统计文件中单词出现的频率。除此之外，它还可以用来处理数据与数据之间没有关系的任务，比如对网页分析、分词等，每个网页可以独立的分析、分词，而这两个网页之间并没有关系。网页几十亿、上百亿，如果单机处理，效率低下，就可以利用 MapReduce 提供的高可靠、高性能、高容错的并行计算框架，并行地处理这几十亿、上百亿的网页。