18 算法思想

• 0.1. 贪心算法
  • 0.1.1. 例子
  • 0.1.2. 定义
  • 0.1.3. 实战
  • 0.1.3.1. 分糖果
  • 0.1.3.2. 钱币找零
  • 0.1.3.3. 区间覆盖
  • 0.1.4. 霍夫曼编码
• 0.2. 分治算法
  • 0.2.1. 分治算法应用
  • 0.2.2. 分治算法海量数据应用
• 0.3. 回溯算法
  • 0.3.1. 经典应用
  • 0.3.1.1. 0-1背包
  • 0.3.1.2. 正则表达式
• 0.4. 动态规划
  • 0.4.1. 动态规划问题模型
  • 0.4.1.1. 0-1背包问题
    • 0.4.1.1.1. 回溯解题
    • 0.4.1.1.2. 动态规划解题
  • 0.4.1.2. -1背包问题升级版
  • 0.4.2. 动态规划理论
  • 0.4.2.1. 具体问题
  • 0.4.3. 动态规划解题思路
  • 0.4.3.1. 状态转移表法
  • 0.4.3.2. 状态转移方程法
  • 0.4.4. 动态规划实战
  • 0.4.4.1. 编程计算莱文斯坦距离
  • 0.4.4.2. 编程计算最长公共子串长度
• 0.5. 四种算法比较
  • 0.5.1. 回溯
  • 0.5.2. 动态规划
  • 0.5.3. 分治
  • 0.5.4. 贪心

0.1. 贪心算法

贪心算法有很多经典的应用，比如：

• 霍夫曼编码（Huffman Coding）
• Prim
• Kruskal 最小生成树算法
• Dijkstra 单源最短路径算法

0.1.1. 例子

1. 假设有一个可以容纳 100kg 物品的背包，可以装各种物品。
2. 有以下 5 种豆子，每种豆子的总量和总价值都各不相同。
3. 为了让背包中所装物品的总价值最大，我们如何选择在背包中装哪些豆子？每种豆子又该装多少呢？

1. 先算一算每个物品的单价，按照单价由高到低依次来装
2. 单价从高到低排列，依次是：黑豆、绿豆、红豆、青豆、黄豆
3. 所以往背包里装 20kg 黑豆、30kg 绿豆、50kg 红豆

这个问题的解决思路本质上就是贪心算法。

0.1.2. 定义

第一步，当看到这个问题的时候，首先要联想到贪心算法：针对一组数据（5种豆子），定义了限制值（100kg）和期望值（总价值），希望从中选出几个数据，在满足限制值的情况下，期望值最大。

第二步，尝试下这个问题是否可以用贪心算法解决：每次选择当前情况下，在对限制值同等贡献量（重量相同）的情况下，对期望值（总价值）贡献最大的数据。

第三步，举几个例子看贪心算法产生的结果是否是最优。大部分情况下，举几个例子验证一下就可以了。严格地证明贪心算法的正确性，是非常复杂的，需要涉及比较多的数学推理。而且，从实践的角度来说，大部分能用贪心算法解决的问题，贪心算法的正确性都是显而易见的，也不需要严格的数学推导证明。

实际上，用贪心算法解决问题的思路，并不总能给出最优解。

在一个有权图中，从顶点 S 开始，找一条到顶点 T 的最短路径（路径中边的权值和最小）。

贪心算法的解决思路是，每次都选择一条跟当前顶点相连的权最小的边，直到找到顶点 T。

按照这种思路，求出的最短路径是 S->A->E->T，路径长度是 1+4+4=9。

但是，这种贪心的选择方式，最终求的路径并不是最短路径，因为路径 S->B->D->T 才是最短路径，路径的长度是 2+2+2=6。

在这个问题上，贪心算法不工作的主要原因是，前面的选择，会影响后面的选择。如果第一步从顶点 S 走到顶点 A，那接下来面对的顶点和边，跟第一步从顶点 S 走到顶点 B，是完全不同的。所以，即便第一步选择最优的走法（边最短），但有可能因为这一步选择，导致后面每一步的选择都很糟糕，最终也就无缘全局最优解了。

0.1.3. 实战

0.1.3.1. 分糖果

有 m 个糖果和 n 个孩子，现在要把糖果分给这些孩子吃，但是糖果少，孩子多（m<n），所以糖果只能分配给一部分孩子。每个糖果的大小不等，这 m 个糖果的大小分别是 s1，s2，s3，……，sm。除此之外，每个孩子对糖果大小的需求也是不一样的，只有糖果的大小大于等于孩子的对糖果大小的需求的时候，孩子才得到满足。假设这 n 个孩子对糖果大小的需求分别是 g1，g2，g3，……，gn。如何分配糖果，能尽可能满足最多数量的孩子？

把这个问题抽象成：

• 一组数据：从 n 个孩子中，抽取一部分孩子分配糖果
• 限制值：糖果个数 m
• 期望值：让满足的孩子的个数是最大的

用贪心算法来解决。

1. 对于一个孩子来说，如果小的糖果可以满足，就没必要用更大的糖果，这样更大的就可以留给其他对糖果大小需求更大的孩子。对糖果大小需求小的孩子更容易被满足，所以从需求小的孩子开始分配糖果。因为满足一个需求大的孩子跟满足一个需求小的孩子，对期望值的贡献是一样的。
2. 每次从剩下的孩子中，找出对糖果大小需求最小的，然后发给他剩下的糖果中能满足他的最小的糖果，这样得到的分配方案，也就是满足的孩子个数最多的方案。

0.1.3.2. 钱币找零

假设有 1 元、2 元、5 元、10 元、20 元、50 元、100 元这些面额的纸币，它们的张数分别是 c1、c2、c5、c10、c20、c50、c100。现在要用这些钱来支付 K 元，最少要用多少张纸币呢？

把这个问题抽象成：

• 一组数据：若干纸币
• 限制值：K元
• 期望值：纸币数量最少

用贪心算法来解决。在贡献相同期望值的情况下，希望多贡献金额。

1. 每次选择小于K元的面额的纸币中面额最大的
2. 选择该面额若干张，保证面额总和小于K
3. 对剩余的值继续上述两个操作

0.1.3.3. 区间覆盖

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

把这个问题抽象成：

• 一组数据：n个区间
• 限制值：区间不相交
• 期望值：区间数量最多

用贪心算法来解决。

1. 假设这 n 个区间中最左端点是 lmin，最右端点是 rmax。这个问题就相当于选择几个不相交的区间，从左到右将[lmin, rmax]覆盖上
2. 按照起始端点从小到大的顺序对这 n 个区间排序
3. 每次选择左端点跟前面的已经覆盖的区间不重合的，右端点又尽量小的，这样可以让剩下的未覆盖区间尽可能的大，就可以放置更多的区间

0.1.4. 霍夫曼编码

霍夫曼编码，利用贪心算法来实现对数据压缩编码，有效节省数据存储空间。

假设有一个包含 1000 个字符的文件，每个字符占 1 个 byte（1byte=8bits），存储这 1000 个字符就一共需要 8000bits，那有没有更加节省空间的存储方式呢？

1. 假设通过统计分析发现，这 1000 个字符中只包含 6 种不同字符，假设它们分别是 a、b、c、d、e、f
2. 而 3 个二进制位（bit）就可以表示 8 个不同的字符，所以，为了尽量减少存储空间，每个字符用 3 个二进制位来表示
3. 存储这 1000 个字符只需要 3000bits 就可以了，比原来的存储方式节省了很多空间

a(000)、b(001)、c(010)、d(011)、e(100)、f(101)

还有更加节省空间的存储方式，霍夫曼编码，一种十分有效的编码方法，广泛用于数据压缩中，其压缩率通常在 20%～90% 之间。

霍夫曼编码不仅会考察文本中有多少个不同字符，还会考察每个字符出现的频率，根据频率的不同，选择不同长度的编码。

霍夫曼编码试图用这种不等长的编码方法，来进一步增加压缩的效率。

如何给不同频率的字符选择不同长度的编码呢？

把这个问题抽象成：

• 一组数据：给定的文本
• 限制值：单个字符的长度
• 期望值：存储空间最小

用贪心算法来解决。

• 把出现频率比较多的字符，用稍微短一些的编码
• 把出现频率比较少的字符，用稍微长一些的编码

对于等长的编码来说，解压缩起来很简单。比如上面例子中abcdef用 3 个 bit 表示一个字符。在解压缩的时候，每次从文本中读取 3 位二进制码，然后翻译成对应的字符。

霍夫曼编码是不等长的，每次应该读取读取的位数无法确定，这个问题就导致霍夫曼编码解压缩起来比较复杂。为了避免解压缩过程中的歧义，霍夫曼编码要求各个字符的编码之间，不会出现某个编码是另一个编码前缀的情况。

1. 假设这 6 个字符出现的频率从高到低依次是 a、b、c、d、e、f。
2. 编码成如下表格，任何一个字符的编码都不是另一个的前缀，在解压缩的时候，每次会读取尽可能长的可解压的二进制串，所以在解压缩的时候也不会歧义。

经过这种编码压缩之后，这 1000 个字符只需要 2100bits 就可以了。

霍夫曼编码中，如何根据字符出现频率的不同，给不同的字符进行不同长度的编码，这里的处理稍微有些技巧。

1. 把每个字符看作一个节点，并且附带着把频率放到优先级队列中
2. 从队列中取出频率最小的两个节点 A、B，然后新建一个节点 C（频率小的放在左边）
3. 把频率设置为两个节点的频率之和，并把这个新节点 C 作为节点 A、B 的父节点
4. 再把 C 节点放入到优先级队列中
5. 重复这个过程，直到队列中没有数据

给每一条边加上一个权值：

• 指向左子节点的边统统标记为 0
• 指向右子节点的边，统统标记为 1

从根节点到叶节点的路径就是叶节点对应字符的霍夫曼编码。

实际上，贪心算法适用的场景比较有限。这种算法思想更多的是指导设计基础算法。比如最小生成树算法、单源最短路径算法，这些算法都用到了贪心算法。

0.2. 分治算法

分治算法（divide and conquer）的核心思想其实就是四个字，分而治之，将原问题划分成 n 个规模较小，并且结构与原问题相似的子问题，递归地解决这些子问题，然后再合并其结果，就得到原问题的解。

分治算法是一种处理问题的思想，递归是一种编程技巧。实际上，分治算法一般都比较适合用递归来实现。分治算法的递归实现中，每一层递归都会涉及这样三个操作：

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

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

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

0.2.1. 分治算法应用

使用分治算法解决排序问题。在排序算法中，用有序度来表示一组数据的有序程度，用逆序度表示一组数据的无序程度。

假设有 n 个数据，期望数据从小到大排列，那完全有序的数据的有序度就是 n(n-1)/2，逆序度等于 0；相反，倒序排列的数据的有序度就是 0，逆序度是 n(n-1)/2。除了这两种极端情况外，通过计算有序对或者逆序对的个数，来表示数据的有序度或逆序度，如何编程求出一组数据的有序对个数或者逆序对个数。

1. 解法一：将每个数字与后面的数字比较，看有几个比它小，记作k，依次类推，每个数都考察一遍，将k值球和，得到逆序对个数。时间复杂度\(O(n^2)\)。
2. 解法二：分治算法，将数组分为前后两部分（A1,A2），分别求逆序对个数（k1,k2），再计算A1和A2之间的逆序对个数k3，求和k1+k2+k3。

分治算法的一个要求是，子问题合并的代价不能太大，否则就起不了降低时间复杂度的效果了。

解法二中如何快速计算出两个子问题 A1 与 A2 之间的逆序对个数呢？可以使用归并排序。归并排序中非常关键的操作，就是将两个有序的小数组，合并成一个有序的数组。实际上，在这个合并的过程中，就可以计算这两个小数组的逆序对个数了。每次合并操作，都计算逆序对个数，把这些计算出来的逆序对个数求和，就是这个数组的逆序对个数了。

0.2.2. 分治算法海量数据应用

分治算法思想的应用是非常广泛的：

• 不仅限于指导编程和算法设计
• 还经常用在海量数据处理的场景中

大部分数据结构和算法都是基于内存存储和单机处理。

但是，如果要处理的数据量非常大，没法一次性放到内存中，这个时候，这些数据结构和算法就无法工作了。

比如，给 10GB 的订单文件按照金额排序这样一个需求，看似是一个简单的排序问题，但是因为数据量大，有 10GB，而单机的内存可能只有 2、3GB，无法一次性加载到内存，也就无法通过单纯地使用快排、归并等基础算法来解决了。

要解决数据量大到内存装不下的问题，利用分治的思想。

1. 将海量的数据集合根据某种方法，划分为几个小的数据集合
2. 每个小的数据集合单独加载到内存来解决
3. 再将小数据集合合并成大数据集合

实际上，利用这种分治的处理思路，不仅仅能克服内存的限制，还能利用多线程或者多机处理，加快处理的速度。

上面的例子，先扫描一遍订单，根据订单的金额，将 10GB 的文件划分为几个金额区间。

• 比如订单金额为 1 到 100 元的放到一个小文件
• 101 到 200 之间的放到另一个文件
• 以此类推

每个小文件都可以单独加载到内存排序，最后将这些有序的小文件合并，就是最终有序的 10GB 订单数据了。

如果订单数据存储在类似 GFS 这样的分布式系统上，当 10GB 的订单被划分成多个小文件的时候，每个文件可以并行加载到多台机器上处理，最后再将结果合并在一起，这样并行处理的速度也加快了很多。但是，注意：数据的存储与计算所在的机器是同一个或者在网络中靠的很近（比如一个局域网内，数据存取速度很快），否则就会因为数据访问的速度，导致整个处理过程不但不会变快，反而有可能变慢。

实际上：

• MapReduce 框架只是一个任务调度器
• 底层依赖 GFS 来存储数据
• 依赖 Borg 管理机器

它从 GFS 中拿数据，交给 Borg 中的机器执行，并且时刻监控机器执行的进度，一旦出现机器宕机、进度卡壳等，就重新从 Borg 中调度一台机器执行。

• 可以用来处理数据与数据之间存在关系的任务，比如 MapReduce 的经典例子，统计文件中单词出现的频率
• 可以用来处理数据与数据之间没有关系的任务，比如对网页分析、分词等，每个网页可以独立的分析、分词，而这两个网页之间并没有关系

0.3. 回溯算法

回溯算法在软件开发场景中的应用：

• 深度优先搜索
• 正则表达式匹配
• 编译原理中语法分析

回溯算法在数学中的应用：

• 数独
• 八皇后
• 0-1背包
• 图的着色
• 旅行商问题
• 全排列

笼统地讲，回溯算法很多时候都应用在“搜索”这类问题上。这里的搜索，并不是狭义的指图的搜索算法，而是广义上的在一组可能的解中，搜索满足期望的解。

回溯的处理思想，有点类似枚举搜索。枚举所有的解，找到满足期望的解。回溯算法非常适合用递归来实现，在实现的过程中，剪枝操作是提高回溯效率的一种技巧。

为了有规律地枚举所有可能的解，避免遗漏和重复，把问题求解的过程分为多个阶段。每个阶段，都会面对一个岔路口，先随意选一条路走，当发现这条路走不通的时候（不符合期望的解），就回退到上一个岔路口，另选一种走法继续走。

举一个经典的回溯例子，八皇后问题。有一个 8x8 的棋盘，希望往里放 8 个棋子（皇后），每个棋子所在的行、列、对角线都不能有另一个棋子。

第一幅图是满足条件的一种方法，第二幅图是不满足条件的。八皇后问题就是期望找到所有满足这种要求的放棋子方式。

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

回溯算法非常适合用递归代码实现。

0.3.1. 经典应用

0.3.1.1. 0-1背包

0-1 背包是非常经典的算法问题，很多场景都可以抽象成这个问题模型。

这个问题的经典解法是动态规划，另一种简单但没有那么高效的解法就是回溯算法。

有一个背包，背包总的承载重量是 Wkg。有 n 个物品，每个物品的重量不等，并且不可分割。现在期望选择几件物品，装载到背包中。在不超过背包所能装载重量的前提下，如何让背包中物品的总重量最大？

显然，这个问题已经无法通过贪心算法来解决了。

用回溯算法如何来解决。

1. 对于每个物品来说，都有两种选择，装进背包或者不装进背包。
2. 对于 n 个物品来说，总的装法就有 \(2^n\) 种，去掉总重量超过 Wkg 的，从剩下的装法中选择总重量最接近 Wkg 的。

如何才能不重复地穷举出这 \(2^n\) 种装法呢？

1. 把物品依次排列，整个问题就分解为了 n 个阶段，每个阶段对应一个物品怎么选择。
2. 先对第一个物品进行处理，选择装进去或者不装进去，然后再递归地处理剩下的物品。

这里还稍微用到了一点搜索剪枝的技巧，就是当发现已经选择的物品的重量超过 Wkg 之后，就停止继续探测剩下的物品。

0.3.1.2. 正则表达式

正则表达式里最重要的一种算法思想就是回溯。

正则表达式中，最重要的就是通配符，通配符结合在一起，可以表达非常丰富的语义。

假设正则表达式中只包含“*”和“?”这两种通配符，并且对这两个通配符的语义稍微做些改变，其中：

• “*”：匹配任意多个（大于等于 0 个）任意字符
• “?”：匹配零个或者一个任意字符

用回溯算法，判断一个给定的文本，能否跟给定的正则表达式匹配？

1. 依次考察正则表达式中的每个字符，当是非通配符时，直接跟文本的字符进行匹配
   1. 如果相同，则继续往下处理
   2. 如果不同，则回溯
2. 如果遇到特殊字符，有多种处理方式了，也就是所谓的岔路口
   1. 比如“*”有多种匹配方案，可以匹配任意个文本串中的字符，就先随意的选择一种匹配方案，然后继续考察剩下的字符
   2. 如果中途发现无法继续匹配下去了，就回到这个岔路口，重新选择一种匹配方案
   3. 然后再继续匹配剩下的字符

0.4. 动态规划

动态规划比较适合用来求解最优问题，比如求最大值、最小值等等。它可以非常显著地降低时间复杂度，提高代码的执行效率。

0.4.1. 动态规划问题模型

0.4.1.1. 0-1背包问题

对于一组不同重量、不可分割的物品，选择一些装入背包，在满足背包最大重量限制的前提下，背包中物品总重量的最大值是多少呢？

使用回溯的解决方法，穷举搜索所有可能的装法，然后找出满足条件的最大值。但是，回溯算法的复杂度比较高，是指数级别的。

寻找规律从而有效降低时间复杂度。

0.4.1.1.1. 回溯解题

• 假设背包的最大承载重量是 9
• 有 5 个不同的物品，重量分别是 2，2，4，6，3

使用回溯求解过程，用递归树画出来，就是下面这个样子：

递归树中的每个节点表示一种状态，用(i,cw)来表示。其中：

• i 表示将要决策第几个物品是否装入背包
• cw 表示当前背包中物品的总重量

比如，（2，2）表示将要决策第 2 个物品是否装入背包，在决策前，背包中物品的总重量是 2。

从递归树中可以看出，有些子问题的求解是重复的，比如图中 f(2, 2) 和 f(3,4) 都被重复计算了两次。

因此，可以使用缓存的方式来优化，记录已经计算好的 f(i,cw)，当再次计算到重复的 f(i,cw) 的时候，可以直接从缓存中取出来结果，不用再递归计算了，这样就可以避免冗余计算。

使用缓存的解决方法非常好。它已经跟动态规划的执行效率基本上没有差别。

时间复杂度：\(O(2^n)\)

0.4.1.1.2. 动态规划解题

1. 把整个求解过程分为 n 个阶段，每个阶段会决策一个物品是否放到背包中
2. 每个物品决策（放入或者不放入背包）完之后，背包中的物品的重量会有多种情况，也就是说，会达到多种不同的状态，对应到递归树中，就是有很多不同的节点
3. 把每一层重复的状态（节点）合并，只记录不同的状态，然后基于上一层的状态集合，来推导下一层的状态集合
4. 通过合并每一层重复的状态，这样就保证每一层不同状态的个数都不会超过 w 个（w 表示背包的承载重量）
5. 成功避免了每层状态个数的指数级增长。用一个二维数组 states[n][w+1]，来记录每层可以达到的不同状态

具体过程：

1. 第 0 个（下标从 0 开始编号）物品的重量是 2，要么装入背包，要么不装入背包
2. 决策完之后，会对应背包的两种状态，背包中物品的总重量是 0 或者 2
3. 用 states[0][0]=true 和 states[0][2]=true 来表示这两种状态
4. 第 1 个物品的重量也是 2，基于之前的背包状态，在这个物品决策完之后，不同的状态有 3 个，背包中物品总重量分别是 0(0+0)，2(0+2 or 2+0)，4(2+2)
5. 用 states[1][0]=true，states[1][2]=true，states[1][4]=true 来表示这三种状态
6. 以此类推
7. 直到考察完所有的物品后，整个 states 状态数组就都计算好

把整个计算的过程画了出来，图中 0 表示 false，1 表示 true。只需要在最后一层，找一个值为 true 的最接近 w（这里是 9）的值，就是背包中物品总重量的最大值。

动态规划解决问题的思路：把问题分解为多个阶段，每个阶段对应一个决策。记录每一个阶段可达的状态集合（去掉重复的），然后通过当前阶段的状态集合，来推导下一个阶段的状态集合，动态地往前推进。

时间复杂度：O(n×w)，n 表示物品个数，w 表示背包可以承载的总重量。

尽管动态规划的执行效率比较高，但是需要额外申请一个 n 乘以 w+1 的二维数组，对空间的消耗比较多。所以，动态规划是一种空间换时间的解决思路。

0.4.1.2. -1背包问题升级版

引入物品价值，对于一组不同重量、不同价值、不可分割的物品，选择将某些物品装入背包，在满足背包最大重量限制的前提下，背包中可装入物品的总价值最大是多少呢？

这个问题依旧可以用回溯算法来解决。画出递归树。在递归树中，每个节点表示一个状态，需要 3 个变量（i, cw, cv）来表示一个状态。其中，i 表示即将要决策第 i 个物品是否装入背包，cw 表示当前背包中物品的总重量，cv 表示当前背包中物品的总价值。

在递归树中，有几个节点的 i 和 cw 是完全相同的，比如 f(2,2,4) 和 f(2,2,3)。在背包中物品总重量一样的情况下，f(2,2,4) 这种状态对应的物品总价值更大，可以舍弃 f(2,2,3) 这种状态，只需要沿着 f(2,2,4) 这条决策路线继续往下决策就可以。也就是说，对于 (i, cw) 相同的不同状态，那我们只需要保留 cv 值最大的那个，继续递归处理，其他状态不予考虑。

使用动态规划来解决这个问题，把整个求解过程分为 n 个阶段，每个阶段会决策一个物品是否放到背包中。每个阶段决策完之后，背包中的物品的总重量以及总价值，会有多种情况，也就是会达到多种不同的状态。

用一个二维数组 states[n][w+1]，来记录每层可以达到的不同状态。不过这里数组存储的值是当前状态对应的最大总价值。把每一层中 (i,cw) 重复的状态（节点）合并，只记录 cv 值最大的那个状态，然后基于这些状态来推导下一层的状态。

0.4.2. 动态规划理论

• 一个模型：多阶段决策最优模型（用动态规划解决最优解问题，解决的过程经历多个决策阶段，每个决策阶段对应一组状态，我们寻找一组决策序列，能够阐释最终期望求解的最优值）
• 三个特征：
  • 最优子结构：问题的最优解包含子问题的最优解（即通过子问题的最优解，推导出问题的最优解），也就是后面阶段的状态可以通过前面阶段的状态推导出来
  • 无后效性：
  • 在推导后面阶段的状态的时候，只关心前面阶段的状态值，不关心这个状态是怎么一步一步推导出来的
  • 某阶段状态一旦确定，就不受之后阶段的决策影响
  • 重复子问题：不同的决策序列，到达某个相同的阶段时，可能会产生重复的状态

0.4.2.1. 具体问题

• 假设有一个 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) 的最短路径长度。这个问题是一个多阶段决策最优解问题，符合动态规划的模型。

把从起始位置 (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) 两个状态推导出来。这就说明，这个问题符合“最优子结构”。

如果走到 (i,j) 这个位置，只能通过 (i-1,j)，(i,j-1) 这两个位置移动过来，也就是说，想要计算 (i,j) 位置对应的状态，只需要关心 (i-1,j)，(i,j-1) 两个位置对应的状态，并不关心棋子是通过什么样的路线到达这两个位置的。而且，仅允许往下和往右移动，不允许后退，所以，前面阶段的状态确定之后，不会被后面阶段的决策所改变，所以，这个问题符合“无后效性”这一特征。

使用回溯算法来解决这个问题。画出递归树就会发现，递归树中有重复的节点。重复的节点表示，从左上角到节点对应的位置，有多种路线，说明这个问题中存在重复子问题。

min_dist(i, j) = w[i][j] + min(min_dist(i,j-1), min_dist(i-1,j))

0.4.3. 动态规划解题思路

0.4.3.1. 状态转移表法

回溯算法实现 - 定义状态 - 画递归树 - 找重复子问题 - 画状态转移表 - 根据递推关系填表 - 将填表过程翻译成代码。

一般能用动态规划解决的问题，都可以使用回溯算法的暴力搜索解决。

1. 当拿到问题的时候，先用简单的回溯算法解决，然后定义状态，每个状态表示一个节点，然后对应画出递归树
2. 从递归树中，很容易看是否存在重复子问题，以及重复子问题是如何产生的
3. 以此来寻找规律，看是否能用动态规划解决
4. 找到重复子问题之后，有两种处理思路
   1. 第一种是直接用回溯加缓存的方法，来避免重复子问题。从执行效率上来讲，这跟动态规划的解决思路没有差别
   2. 第二种是使用动态规划的解决方法：状态转移表法

先画出一个状态表。状态表一般都是二维的，把它想象成二维数组。其中，每个状态包含三个变量，行、列、数组值。

1. 根据决策的先后过程，从前往后，根据递推关系，分阶段填充状态表中的每个状态
2. 最后，将这个递推填表的过程，翻译成代码，就是动态规划代码

尽管大部分状态表都是二维的，但是如果问题的状态比较复杂，需要很多变量来表示，那对应的状态表可能就是高维的，比如三维、四维。那就不适合用状态转移表法来解决了。

• 一方面是因为高维状态转移表不好画图表示
• 另一方面因为人脑确实很不擅长思考高维的东西

如何用这个状态转移表法，来解决上面那个矩阵最短路径的问题。

1. 从起点到终点，有很多种不同的走法。可以穷举所有走法，然后对比找出一个最短走法
2. 如何才能无重复又不遗漏地穷举出所有走法，可以用回溯算法这个比较有规律的穷举算法
3. 有了回溯代码，要画出递归树，以此来寻找重复子问题
4. 在递归树中，一个状态（也就是一个节点）包含三个变量 (i, j, dist)，其中 i，j 分别表示行和列，dist 表示从起点到达 (i,j) 的路径长度
5. 从图中看出，尽管 (i, j, dist) 不存在重复的，但是 (i, j) 重复的有很多
6. 对于 (i,j) 重复的节点，只需要选择 dist 最小的节点，继续递归求解，其他节点就可以舍弃了

既然存在重复子问题，就可以尝试用动态规划来解决。

画出一个二维状态表，表中的行、列表示棋子所在的位置，表中的数值表示从起点到这个位置的最短路径。按照决策过程，通过不断状态递推演进，将状态表填好。

0.4.3.2. 状态转移方程法

找最优子结构 - 写状态转移方程 - 将状态转移方程翻译成代码。

状态转移方程法有点类似递归的解题思路。

1. 分析某个问题如何通过子问题（最优子结构）来递归求解
2. 根据最优子结构，写出递归公式（状态转移方程）
3. 有了状态转移方程，代码实现就非常简单了，一般情况下，我们有两种代码实现方法
   1. 一种是递归加缓存
   2. 另一种是迭代递推

还是以上面的例子为例，状态转移方程min_dist(i, j) = w[i][j] + min(min_dist(i, j-1), min_dist(i-1, j))。

这里我强调一下，状态转移方程是解决动态规划的关键。

• 如果能写出状态转移方程，那动态规划问题基本上就解决一大半了，而翻译成代码非常简单
• 但是很多动态规划问题的状态本身就不好定义，状态转移方程也就更不好想到

0.4.4. 动态规划实战

量化两个字符串的相似度：编辑距离。

编辑距离：将一个字符串转化成另一个字符串，需要的最少编辑操作次数（比如增加一个字符、删除一个字符、替换一个字符）。编辑距离越大，说明两个字符串的相似程度越小；相反，编辑距离就越小，说明两个字符串的相似程度越大。对于两个完全相同的字符串来说，编辑距离就是 0。

根据所包含的编辑操作种类的不同，编辑距离有多种不同的计算方式，比较著名的有：

• 莱文斯坦距离（Levenshtein distance）：允许增加、删除、替换字符这三个编辑操作；莱文斯坦距离的大小，表示两个字符串差异的大小
• 最长公共子串长度（Longest common substring length）：允许增加、删除字符这两个编辑操作；而最长公共子串的大小，表示两个字符串相似程度的大小

两个字符串 mitcmu 和 mtacnu 它们的莱文斯坦距离是 3，最长公共子串长度是 4。

0.4.4.1. 编程计算莱文斯坦距离

这个问题是求把一个字符串变成另一个字符串，需要的最少编辑次数。整个求解过程，涉及多个决策阶段，依次考察一个字符串中的每个字符，跟另一个字符串中的字符是否匹配，匹配的话如何处理，不匹配的话又如何处理。所以，这个问题符合多阶段决策最优解模型（贪心、回溯、动态规划可以解决的问题，都可以抽象成这样一个模型）。

回溯是一个递归处理的过程：

• 如果 a[i]与 b[j]匹配，递归考察 a[i+1]和 b[j+1]
• 如果 a[i]与 b[j]不匹配，有多种处理方式可选：
  • 可以删除 a[i]，然后递归考察 a[i+1]和 b[j]
  • 可以删除 b[j]，然后递归考察 a[i]和 b[j+1]
  • 可以在 a[i]前面添加一个跟 b[j]相同的字符，然后递归考察 a[i]和 b[j+1]
  • 可以在 b[j]前面添加一个跟 a[i]相同的字符，然后递归考察 a[i+1]和 b[j]
  • 可以将 a[i]替换成 b[j]，或者将 b[j]替换成 a[i]，然后递归考察 a[i+1]和 b[j+1]

根据回溯算法的实现画出递归树，看是否存在重复子问题。如果存在重复子问题，就可以考虑能否用动态规划来解决；如果不存在重复子问题，那回溯就是最好的解决方法。

在递归树中，每个节点代表一个状态，状态包含三个变量 (i,j,edist)，其中，edist 表示处理到 a[i]和 b[j]时，已经执行的编辑操作的次数。

在递归树中，(i,j) 两个变量重复的节点很多，比如 (3, 2) 和 (2, 3)。对于 (i,j) 相同的节点，只需要保留 edist 最小的，继续递归处理就可以了，剩下的节点都可以舍弃。

所以，状态就从 (i,j,edist) 变成了 (i,j,min_edist)，其中，min_edist 表示处理到 a[i]和 b[j]，已经执行的最少编辑次数。

这个问题符合动态规划，但是，状态转移方式要复杂很多，状态 (i,j) 可能从 (i-1,j)，(i,j-1)，(i-1,j-1) 三个状态中的任意一个转移过来。基于刚刚的分析，把状态转移的过程，用公式写出来，就是状态转移方程。

// 如果：a[i]!=b[j]，那么：min_edist(i,j)就等于：
min(min_edist(i-1,j)+1, min_edist(i,j-1)+1, min_edist(i-1,j-1)+1)

// 如果：a[i]==b[j]，那么：min_edist(i,j)就等于：
min(min_edist(i-1,j)+1, min_edist(i,j-1)+1，min_edist(i-1,j-1))

// 其中，min表示求三数中的最小值。

了解了状态与状态之间的递推关系，画出一个二维的状态表，按行依次来填充状态表中的每个值。

既有状态转移方程，又理清了完整的填表过程，代码实现就非常简单了。

关于复杂算法问题的解决思路的一些经验和技巧：

1. 当拿到一个问题的时候，先不思考，计算机会如何实现这个问题，而是单纯考虑“人脑”会如何去解决这个问题。人脑比较倾向于思考具象化的、摸得着看得见的东西，不适合思考过于抽象的问题。
2. 把抽象问题具象化，可以实例化几个测试数据，通过人脑去分析具体实例的解，然后总结规律，再尝试套用学过的算法，看是否能够解决。
3. 看到问题，立马想到能否用动态规划解决，然后直接就可以寻找最优子结构，写出动态规划方程，然后将状态转移方程翻译成代码。

0.4.4.2. 编程计算最长公共子串长度

最长公共子串作为编辑距离中的一种，只允许增加、删除字符两种编辑操作。从本质上来说，它表征的也是两个字符串之间的相似程度。这个问题的解决思路，跟莱文斯坦距离的解决思路非常相似，也可以用动态规划解决。

每个状态包括三个变量 (i, j, max_lcs)，max_lcs 表示 a[0…i]和 b[0…j]的最长公共子串长度。

回溯的处理思路：

1. 从 a[0]和 b[0]开始，依次考察两个字符串中的字符是否匹配
2. 如果 a[i]与 b[j]互相匹配，将最大公共子串长度加一，并且继续考察 a[i+1]和 b[j+1]
3. 如果 a[i]与 b[j]不匹配，最长公共子串长度不变，这个时候，有两个不同的决策路线：
   1. 删除 a[i]，或者在 b[j]前面加上一个字符 a[i]，然后继续考察 a[i+1]和 b[j]
   2. 删除 b[j]，或者在 a[i]前面加上一个字符 b[j]，然后继续考察 a[i]和 b[j+1]

反过来也就是说，要求 a[0…i]和 b[0…j]的最长公共长度 max_lcs(i,j)，只有可能通过下面三个状态转移过来：

• (i-1,j-1,max_lcs)，其中 max_lcs 表示 a[0…i-1]和 b[0…j-1]的最长公共子串长度
• (i-1,j,max_lcs)，其中 max_lcs 表示 a[0…i-1]和 b[0…j]的最长公共子串长度
• (i,j-1,max_lcs)，其中 max_lcs 表示 a[0…i]和 b[0…j-1]的最长公共子串长度

把这个转移过程，用状态转移方程写出来，就是下面这个样子：

// 如果：a[i]==b[j]，那么：max_lcs(i, j)就等于：
max(max_lcs(i-1,j-1)+1, max_lcs(i-1, j), max_lcs(i, j-1))；

// 如果：a[i]!=b[j]，那么：max_lcs(i, j)就等于：
max(max_lcs(i-1,j-1), max_lcs(i-1, j), max_lcs(i, j-1))；

// 其中max表示求三数中的最大值。

0.5. 四种算法比较

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

0.5.1. 回溯

• 回溯算法是个“万金油”。基本上能用的动态规划、贪心解决的问题，我们都可以用回溯算法解决
• 回溯算法相当于穷举搜索。穷举所有的情况，然后对比得到最优解
• 回溯算法的时间复杂度非常高，是指数级别的，只能用来解决小规模数据的问题。对于大规模数据的问题，用回溯算法解决的执行效率就很低了

0.5.2. 动态规划

• 尽管动态规划比回溯算法高效，但是，并不是所有问题，都可以用动态规划来解决
• 能用动态规划解决的问题，需要满足三个特征，最优子结构、无后效性和重复子问题

0.5.3. 分治

• 在重复子问题这一点上，动态规划和分治算法的区分非常明显
• 分治算法要求分割成的子问题，不能有重复子问题
• 而动态规划正好相反，动态规划之所以高效，就是因为回溯算法实现中存在大量的重复子问题

0.5.4. 贪心

• 贪心算法实际上是动态规划算法的一种特殊情况。它解决问题起来更加高效，代码实现也更加简洁。
• 它可以解决的问题也更加有限。它能解决的问题需要满足三个条件，最优子结构、无后效性和贪心选择性（这里不强调重复子问题）。其中，最优子结构、无后效性跟动态规划中的无异。
• “贪心选择性”的意思是，通过局部最优的选择，能产生全局的最优选择。每一个阶段，都选择当前看起来最优的决策，所有阶段的决策完成之后，最终由这些局部最优解构成全局最优解。