算法思维

贪心算法

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

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

例子

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

物品

总量(KG)

总价值(元)

黄豆

100

绿豆

红豆

120

黑豆

青豆

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

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

定义

第一步，当看到这个问题的时候，首先要联想到贪心算法：针对一组数据（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，是完全不同的。所以，即便第一步选择最优的走法（边最短），但有可能因为这一步选择，导致后面每一步的选择都很糟糕，最终也就无缘全局最优解了。

实战

分糖果

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

把这个问题抽象成：

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

用贪心算法来解决。

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

钱币找零

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

把这个问题抽象成：

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

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

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

区间覆盖

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

把这个问题抽象成：

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

用贪心算法来解决。

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

霍夫曼编码

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

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

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

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

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

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

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

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

把这个问题抽象成：

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

用贪心算法来解决。

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

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

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

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

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

字符

出现频率

编码

总二进制位数

450

350

700

001

270

0001

150

00000

100

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

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

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

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

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

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

分治算法

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

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

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

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

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

分治算法应用

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

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

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

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

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

分治算法海量数据应用

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

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

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

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

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

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

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

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

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

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

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

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

实际上：

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

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

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

回溯算法

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

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

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

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

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

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

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

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

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

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

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

经典应用

0-1背包

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

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

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

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

用回溯算法如何来解决。

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

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

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

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

正则表达式

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

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

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

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

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

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

动态规划

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

动态规划问题模型

0-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)$

动态规划解题

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

具体过程：

第 0 个（下标从 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 状态数组就都计算好

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

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

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

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

-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 值最大的那个状态，然后基于这些状态来推导下一层的状态。

动态规划理论

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

具体问题

假设有一个 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))

动态规划解题思路

状态转移表法

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

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

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

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

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

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

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

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

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

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

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

状态转移方程法

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

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

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

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

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

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

动态规划实战

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

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

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

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

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

编程计算莱文斯坦距离

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

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

如果 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表示求三数中的最小值。

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

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

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

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

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

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

回溯的处理思路：

从 a[0]和 b[0]开始，依次考察两个字符串中的字符是否匹配
如果 a[i]与 b[j]互相匹配，将最大公共子串长度加一，并且继续考察 a[i+1]和 b[j+1]
如果 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表示求三数中的最大值。

四种算法比较

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

回溯

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

动态规划

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

分治

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

贪心

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

上一页复杂度分析下一页Leetcode刷题列表

最后更新于4年前

这有帮助吗？