算法设计知识点整理

基础知识

渐进符号

渐进紧确界、渐进上界、渐进下界。

三种符号图例如下：

分析方法

三种分析标准：最好情况分析、最差情况分析、平均（期望）情况分析。

和式求解

，，。

主定理法

对形如的递归式，存在解。

进一步推导得出：当时，存在；当时，存在；当时，存在。

特别的，如果的形式为，则可进一步简化为：当时，存在；当时，存在；当时，存在。

分治算法

算法原理

分解为子问题，递归求解，合并子问题。

经典问题

归并排序

对于一串数字数组进行排序。将原数组不断划分为小数组，直至该数组元素为，在进行比较。完成小数组比较后，比较合并数组。时间复杂度。

对数列从小到大排序。

分组为。

第一次归并后，第二次归并后，第三次归并后。

最大子数组

在给定的数字数组（包含正数和负数）中，找到一个连续的子数组，使得这个子数组的元素和最大。将原数组不断划分为小数组，直至该数组元素为，计算元素和最大值。合并时比较中点左侧最大值，中点右侧最大值，跨中点最大值。时间复杂度为。

对数列求最大子数组和。

分组为。

合并，左最大值为，右最大值为，跨中点最大值为；合并，左最大值为，右最大值为，跨中点最大值；合并，左最大值为，右最大值为，跨中点最大值为；合并，左最大值为，右最大值为，跨中点最大值为。因此最后最大值为，子数组为。

逆序计数

在给定的数字数组中，计算逆序对（且）的数量。将原数组不断划分为小数组，直至该数组元素为，分别计算每一组的逆序对数量。合并时新的逆序对数量等于中点左侧数量加中点右侧数量加跨中点数量。合并时按照归并排序的方式，可以方便计算跨中点数量。时间复杂度为。

计算中逆序对数量。

分组为。

第一次归并后，数量为；第二次归并后，数量为；第三次归并后，数量为。

快速排序

对于一串数字数组进行排序。选定基准数（多为最右元素），将现数组分区，小于大于基准的分开放在左右侧，并将基准元素放在分界线处。递归继续对左右侧的数组排序，直至递归到单元素数组。时间复杂度为，最差情况下时间复杂度为。

对数列从小到大排序。

以为基准，遍历到时，调换与的位置；遍历到时，调换与的位置；完成遍历后，调换和的位置，并对和递归排序。

排序代码如下：

def qsort(arr, low, high):
    if low < high:
        pivot = arr[high]
        i = low
        for j in range(low, high):
            if arr[j] <= pivot:
                arr[i], arr[j] = arr[j], arr[i]
                i = i + 1 # 保证arr[i]始终是从左数第一个大于基准的元素（初始i==j，直至arr[j]>pivot）
        arr[i], arr[high] = arr[high], arr[i]
    	qsort(arr, low, i - 1)
        qsort(arr, i + 1, high)

次序选择

在一个未排序的序列中找到第小的元素。借助快速排序的思路，在获得基准位置后，比较基准位置与的大小，时遍历右侧数组元素寻找第小元素；时遍历左侧数组元素寻找第小元素；时基准元素即是所求。时间复杂度为。

动态规划

算法原理

确定转移方程，边界条件。使用时需要保证子问题的完整性，不能更改子问题部分的解。

经典问题

0-1背包

给定一组物品，每种物品都有重量和价值，物品不可以切割，放入限定重量的背包中，要求总价值最大。设立动态规划数组代表前个物体放入限重为的背包中最大数量。则存在转移方程和以及边界条件。时间复杂度为。

有一组物品：，放入一个容量为的背包中，使得总价值最大。

dp[i][j] 0 1 2 3 4 5 6

0 0 0 0 0 0 0 0

1 0 0 0 20 20 20 20

2 0 0 0 20 30 30 30

3 0 0 15 20 30 35 45

4 0 0 15 20 30 35 45

最终放入背包的是。

dp[i][j]	2	3	4	5	6
0	0	0	0	0	0
1	0	20	20	20	20
2	0	20	30	30	30
3	15	20	30	35	45
4	15	20	30	35	45

最大子数组

在给定的数字数组（包含正数和负数）中，找到一个连续的子数组，使得这个子数组的元素和最大。设立动态规划数组代表以数组元素作为最后一个元素的子数组的元素和。则存在转移方程和，以及边界条件和。完成全部数组元素计算后，挑选其中最大值即可。时间复杂度为。

对数列求最大子数组和。

dp[i] 0 1 2 3 4 5 6 7 8 9

0 -2 1 -2 4 3 5 6 1 5

最终子数组为。

dp[i]	0	1	2	3	4	5	6	7	8	9
	0	-2	1	-2	4	3	5	6	1	5

最长公共子序列

在两个数组中，找出最长的、保持相对次序的（可不连续）公共元素序列。设立动态规划数组代表两个子数组与之间的公共子序列长度。则存在转移方程和。边界条件。时间复杂度为。

给定序列”ABCDGHA”和”AEDFHR”，求最长公共子序列。

dp[i][j] 0 1A 2B 3C 4D 5G 6H 7A

0 0 0 0 0 0 0 0 0

1A 0 1 1 1 1 1 1 1

2E 0 1 1 1 1 1 1 1

3D 0 1 1 1 2 2 2 2

4F 0 1 1 1 2 2 2 2

5H 0 1 1 1 2 2 3 3

6R 0 1 1 1 2 2 3 3

最终最长公共子序列为 “ADH” 。

dp[i][j]	1A	2B	3C	4D	5G	6H	7A
0	0	0	0	0	0	0	0
1A	1	1	1	1	1	1	1
2E	1	1	1	1	1	1	1
3D	1	1	1	2	2	2	2
4F	1	1	1	2	2	2	2
5H	1	1	1	2	2	3	3
6R	1	1	1	2	2	3	3

最长公共子串

在两个数组中，找出最长的、连续的公共元素序列。设立动态规划数组代表以元素与作为尾元素（可不相同，不同时为0，代表不存在）的公共子串长度。则存在转移方程和。完成全部数组元素计算后，挑选其中最大值即可。边界条件。时间复杂度为。

给定序列”abcdefg”和”zabcdxyz”，求最长公共子串。

dp[i][j] 0 1z 2a 3b 4c 5d 6x 7y 8z

0 0 0 0 0 0 0 0 0 0

1a 0 0 1 0 0 0 0 0 0

2b 0 0 0 2 0 0 0 0 0

3c 0 0 0 0 3 0 0 0 0

4d 0 0 0 0 0 4 0 0 0

5e 0 0 0 0 0 0 0 0 0

6f 0 0 0 0 0 0 0 0 0

7g 0 0 0 0 0 0 0 0 0

最终最长公共子串为 “abcd” 。

dp[i][j]	2a	3b	4c	5d
0	0	0	0	0
1a	1	0	0	0
2b	0	2	0	0
3c	0	0	3	0
4d	0	0	0	4
5e	0	0	0	0
6f	0	0	0	0
7g	0	0	0	0

最小编辑距离

使用最少的插入、替换、删除操作，将一个字符串转换到另一个字符串。设立动态规划数组代表从子串转换到需要的最小操作数量。则此时两个元素相同时不需要进行任何操作，即存在转移方程；此时两个元素不相同时可以替换、插入、删除，即存在转移方程。边界条件（目标字符串为空时全部执行删除操作）和（原字符串为空时全部执行插入操作）。时间复杂度。

给定序列”kitten”和”sitting”，求最小编辑次数。

dp[i][j] 0 1k 2i 3t 4t 5e 6n

0 0 1 2 3 4 5 6

1s 1 1 2 3 4 5 6

2i 2 2 1 2 3 4 5

3t 3 3 2 1 2 3 4

4t 4 4 3 2 1 2 3

5i 5 5 4 3 2 2 3

6n 6 6 5 4 3 3 2

7g 7 7 6 5 4 4 3

最终最小编辑次数为，编辑操作为 , , 。

dp[i][j]	0	1k	2i	3t	4t	5e	6n
0	0	1	2	3	4	5	6
1s	1	1	2	3	4	5	6
2i	2	2	1	2	3	4	5
3t	3	3	2	1	2	3	4
4t	4	4	3	2	1	2	3
5i	5	5	4	3	2	2	3
6n	6	6	5	4	3	3	2
7g	7	7	6	5	4	4	3

贪心算法

算法原理

构造贪心选择，方案正确性证明（重点）。

证明方法一般有：

微扰法（邻项交换）：证明在任意状态下，任何对局部最优策略的微小改变都会造成整体结果变差。有时也会用相邻项交换，证明可以参考冒泡排序正确性证明。
范围缩放：证明任何对局部最优策略作用范围的扩展都不会造成整体结果变差。
决策包容性：证明在任意状态下，做出局部最优策略之后，在问题状态空间中的可达集合包含了作出其它任何决策后的可达集合。即：这个局部最优策略提供的可能性包含其它所有策略提供的可能性。
反证法。
数学归纳法。

经典问题

部分背包

给定一组物品，每种物品都有重量和价值，物品可以切割，放入限定重量的背包中，要求总价值最大。计算比价值（ $价值重量$ ），从大到小排序并按序放入背包。时间复杂度为。

证明可以使用微扰法：设划定重量可以存放比价值为（）的货物，则这部分价值一定存在，应该选择比价值更高的号物品。

霍夫曼编码

霍夫曼编码是将原字符变为01数字串的编码，给定一系列符号以及使用频率，给每个符号分配编码，使得最终翻译后的数字串没有二义性且最短。按照频率构建最小堆（子节点一定大于等于父节点），接着合并节点，直至构建出霍夫曼树，按照节点位置即可获得每个符号的霍夫曼编码。时间复杂度为。

证明可以使用反证法：如果霍夫曼获得的编码组不是最优解，则一定存在一个更优编码组，且中至少有一个节点的编码长度与中某一节点的编码长度不同。如果的编码长度短于的编码长度，则的编码一定会是其他某一个节点的编码或编码的前缀，会造成翻译的二义性；如果的编码长度长于的编码长度，则最终的编码长度一定大于最终的编码长度。

一系列符号及使用频率如下，建立霍夫曼树。

最小堆如下：
1
2
3
4
5
     B
   / \
A   D
   \
     C
初始排序为；第一次合并，合并后；第二次合并，合并后；第三次合并，合并后。合并后霍夫曼树如下：
1
2
3
4
5
        33
      /    \
     12     21
   /  \   /  \
B    D A    C  
最终编码为 , , , 。

活动选择

给定一系列具有开始和结束时刻的活动，选择尽可能多的活动，并使得这些活动参与时间无重叠。按照结束时间从小到达排序，选择结束时刻更早的一系列活动。时间复杂度为。

证明可以使用反证法：如果该算法获得的选择不是最优选择，则一定存在一个更优选择，且中至少有一个活动的结束时间晚于中某一活动的结束时间（假设与是与中第一对不相同的活动）。如果之后的活动都可以正常进行，那么用结束时间更早的替换，之后的活动也一定都可以正常进行。则中的活动数一定大于等于中的活动数。

图算法

图的基本概念

图由点（Vertice）和边（Edge）构成，可表示为。

度是指和点相连的边的数量，等于入度与出度之和。

路径是指从起点到终点一系列相连边所组成的集合（如果一条路径每个顶点只经过一次，即无环路，则称其为简单路径）。

如果两个点之间有一条路径，那么称为两点是连通的，可达的。

是的子图当且仅当。如果等于中连通各点的边的集合，则称是索引子图。

图搜索算法

有多种搜索问题，搜索从一个顶点到另一个顶点的全部路径，从一个顶点出发遍历全图等等。

广度优先搜索

设置一个队列存储待搜索点的顺序。每次出队一个节点元素，从这个节点出发，将周边节点全部加入队列中，继续搜索，直至完成目标。搜索全图的时间复杂度为。

深度优先搜索

从一个节点出发，搜索其周边节点，将其中一个周边节点加入路径，并从该节点出发继续搜索，直至完成目标。搜索全图的时间复杂度为。

环路检测

检测图中是否存在环路或存在环路的个数。可以使用广度优先遍历或深度优先遍历完成。

拓扑排序

在有向无环图中，按照排序规则（若存在路径，则将排在后面），将图转换为一个线性序列。设置两个队列和，分别存储入度为的节点和最终的排序。当队列非空时，出队一个元素，将其加入，并遍历其周边节点，删除连接边，如果删除连接边后周边节点入度为则加入。时间复杂度为。

对于下图进行拓扑排序。

Q T

0

614 0

143 06

432 061

32 0614

2 06143

75 061432

58 0614327

8 06143275

9 061432758

0614327589

最终顺序为。

Q	T
0
614	0
143	06
432	061
32	0614
2	06143
75	061432
58	0614327
8	06143275
9	061432758
	0614327589

强连通分量

强连通指两个节点、间有的有向路径和的有向路径，称间强连通。强连通图指任意两个顶点间都强连通的有向图，而有向图的极大强连通子图称为强连通分量。首先遍历原图的反向图（全部有向边方向反转），得到反向图中的遍历顺序队列（实际上是递归程序的输出顺序），将其反向输出得到队列作为原图的遍历顺序，使用DFS遍历未访问节点即可。时间复杂度为。

求下图全部强连通分量。

原图的反向图为：

从节点出发深度优先遍历确定：。

反向输出得到：。

按照顺序对每个未访问节点开始遍历：

node visited L

10 10,11,12 1,4,6,7,8,9,5,2,3

1 1,2,3,4,6,7 8,9,5

8 8,9 5

5 5

因此最终该图的强连通分量有。

node	visited	L
10	10,11,12	1,4,6,7,8,9,5,2,3
1	1,2,3,4,6,7	8,9,5
8	8,9	5
5	5

最小生成树

在一个连通加权无向图中，如果树包含的全部顶点，则称其为的一个生成树。在这些生成树中，边权值加和最小的称为最小生成树。

Prim

维护一个数组表示已经加入树的节点。选择一个初始节点，从该节点出发，依次将与树相连接（指一个节点在树中，一个节点不在树中）的最小边加入树中，直至全部节点都在树中。时间复杂度为。

求下图的最小生成树。

边队列

1 2,3,4,5,6,7 (1,2),(1,3)

1,2 3,4,5,6,7 (1,2) (1,3),(2,3),(2,4),(2,5)

1,2,3 4,5,6,7 (1,2),(1,3) (2,4),(2,5),(3,4),(3,6)

1,2,3,6 4,5,7 (1,2),(1,3),(3,6) (2,4),(2,5),(3,4),(6,4),(6,5),(6,7)

1,2,3,4,6 5,7 (1,2),(1,3),(3,6),(3,4) (2,5),(6,5),(6,7),(4,5)

1,2,3,4,6,7 5 (1,2),(1,3),(3,6),(3,4),(6,7) (2,5),(6,5),(4,5),(7,5)

1,2,3,4,5,6,7 (1,2),(1,3),(3,6),(3,4),(6,7),(6,5)

最终生成树中边集合为。

			边队列
1	2,3,4,5,6,7		(1,2),(1,3)
1,2	3,4,5,6,7	(1,2)	(1,3),(2,3),(2,4),(2,5)
1,2,3	4,5,6,7	(1,2),(1,3)	(2,4),(2,5),(3,4),(3,6)
1,2,3,6	4,5,7	(1,2),(1,3),(3,6)	(2,4),(2,5),(3,4),(6,4),(6,5),(6,7)
1,2,3,4,6	5,7	(1,2),(1,3),(3,6),(3,4)	(2,5),(6,5),(6,7),(4,5)
1,2,3,4,6,7	5	(1,2),(1,3),(3,6),(3,4),(6,7)	(2,5),(6,5),(4,5),(7,5)
1,2,3,4,5,6,7		(1,2),(1,3),(3,6),(3,4),(6,7),(6,5)

Kruskal

维护一个数组表示已经加入树的节点。将图的边按照权重由小到大排序，从最小边开始，将边一个个放入树中，如果加入该边会构成环路则不加（可以通过判断该边的两个端点是否在树中来判断）。时间复杂度为。因为，所以时间复杂度也可表示为。

求下图的最小生成树。

边边队列

(3,6) 1 (3,6),(3,4),(4,6),(6,7),(1,2),(5,6),(5,7),(4,5),(1,3),(2,4),(2,3),(2,5)

3,6 (3,6) (3,4) 2 (3,4),(4,6),(6,7),(1,2),(5,6),(5,7),(4,5),(1,3),(2,4),(2,3),(2,5)

3,4,6 (3,6),(3,4) (4,6) 2 (4,6),(6,7),(1,2),(5,6),(5,7),(4,5),(1,3),(2,4),(2,3),(2,5)

3,4,6 (3,6),(3,4) (6,7) 2 (6,7),(1,2),(5,6),(5,7),(4,5),(1,3),(2,4),(2,3),(2,5)

3,4,6,7 (3,6),(3,4),(6,7) (1,2) 4 (1,2),(5,6),(5,7),(4,5),(1,3),(2,4),(2,3),(2,5)

1,2,3,4,6,7 (3,6),(3,4),(6,7),(1,2) (5,6) 5 (5,6),(5,7),(4,5),(1,3),(2,4),(2,3),(2,5)

1,2,3,4,5,6,7 (3,6),(3,4),(6,7),(1,2),(5,6) (5,7) 6 (5,7),(4,5),(1,3),(2,4),(2,3),(2,5)

1,2,3,4,5,6,7 (3,6),(3,4),(6,7),(1,2),(5,6) (4,5) 7 (4,5),(1,3),(2,4),(2,3),(2,5)

1,2,3,4,5,6,7 (3,6),(3,4),(6,7),(1,2),(5,6) (1,3) 8 (1,3),(2,4),(2,3),(2,5)

1,2,3,4,5,6,7 (3,6),(3,4),(6,7),(1,2),(5,6),(1,3) (2,4) 8 (2,4),(2,3),(2,5)

1,2,3,4,5,6,7 (3,6),(3,4),(6,7),(1,2),(5,6),(1,3) (2,3) 9 (2,3),(2,5)

1,2,3,4,5,6,7 (3,6),(3,4),(6,7),(1,2),(5,6),(1,3) (2,5) 10 (2,5)

1,2,3,4,5,6,7 (3,6),(3,4),(6,7),(1,2),(5,6),(1,3)

最终生成树中边集合为。

		边	边队列
		(3,6) 1	(3,6),(3,4),(4,6),(6,7),(1,2),(5,6),(5,7),(4,5),(1,3),(2,4),(2,3),(2,5)
3,6	(3,6)	(3,4) 2	(3,4),(4,6),(6,7),(1,2),(5,6),(5,7),(4,5),(1,3),(2,4),(2,3),(2,5)
3,4,6	(3,6),(3,4)	(4,6) 2	(4,6),(6,7),(1,2),(5,6),(5,7),(4,5),(1,3),(2,4),(2,3),(2,5)
3,4,6	(3,6),(3,4)	(6,7) 2	(6,7),(1,2),(5,6),(5,7),(4,5),(1,3),(2,4),(2,3),(2,5)
3,4,6,7	(3,6),(3,4),(6,7)	(1,2) 4	(1,2),(5,6),(5,7),(4,5),(1,3),(2,4),(2,3),(2,5)
1,2,3,4,6,7	(3,6),(3,4),(6,7),(1,2)	(5,6) 5	(5,6),(5,7),(4,5),(1,3),(2,4),(2,3),(2,5)
1,2,3,4,5,6,7	(3,6),(3,4),(6,7),(1,2),(5,6)	(5,7) 6	(5,7),(4,5),(1,3),(2,4),(2,3),(2,5)
1,2,3,4,5,6,7	(3,6),(3,4),(6,7),(1,2),(5,6)	(4,5) 7	(4,5),(1,3),(2,4),(2,3),(2,5)
1,2,3,4,5,6,7	(3,6),(3,4),(6,7),(1,2),(5,6)	(1,3) 8	(1,3),(2,4),(2,3),(2,5)
1,2,3,4,5,6,7	(3,6),(3,4),(6,7),(1,2),(5,6),(1,3)	(2,4) 8	(2,4),(2,3),(2,5)
1,2,3,4,5,6,7	(3,6),(3,4),(6,7),(1,2),(5,6),(1,3)	(2,3) 9	(2,3),(2,5)
1,2,3,4,5,6,7	(3,6),(3,4),(6,7),(1,2),(5,6),(1,3)	(2,5) 10	(2,5)
1,2,3,4,5,6,7	(3,6),(3,4),(6,7),(1,2),(5,6),(1,3)

单源最短路径

在一个连通加权无向图中，求某个节点到其余所有节点的最短路径。

Dijkstra

迪杰斯特拉算法要求图的所有权重都是正数。维护一个优先队列（小顶堆）表示起始点到各节点的最短距离，起始点初始值设为，其余初始值均设为。选取值最小的点，更新其周边节点的值为，直至遍历所有节点。实际上是一种广度优先的遍历思想。时间复杂度。

求下图中各点到的最小距离。

当前节点已搜寻节点最短路径数组

初始

0 0

1 0,1

7 0,1,7

6 0,1,6,7

5 0,1,5,6,7

2 0,1,2,5,6,7

8 0,1,2,5,6,7,8

3 0,1,2,3,5,6,7,8

4 0,1,2,3,4,5,6,7,8

最终各点到的最短路径距离为。

当前节点	已搜寻节点	最短路径数组
初始
0	0
1	0,1
7	0,1,7
6	0,1,6,7
5	0,1,5,6,7
2	0,1,2,5,6,7
8	0,1,2,5,6,7,8
3	0,1,2,3,5,6,7,8
4	0,1,2,3,4,5,6,7,8

Bellman-Ford

贝尔曼-福特算法不要求图中边的权重都为正数，可以完成边权重为负数的最短距离求解（但如果图中出现环，且权重和小于，则无法求解）。维护一个优先队列（小顶堆）表示起始点到各节点的最短距离，起始点初始值设为，其余初始值均设为。从起始点出发，更新其周边节点的值为，直至所有节点的最小距离不再变化（进行迭代，迭代次数最多为）。时间复杂度。

求下图中各点到的最小距离。

当前节点最短路径数组

1

2

3

4

1

2

3

4

最终各点到的最短路径距离为。

点对最短路径

在一个连通加权无向图中，权重可为负数，求任意两个节点间的最短路径。主要使用 Floyd 算法：维护两个二维数组最小距离、最小距离时到达前的一个节点。从起始点出发，以每一个点为中间节点，查询每一条包含该点的路径，并进行距离的更新：对任意存在、，则更新，同时根据距离取值决定是否更新。迭代，直至距离数组不再更新（迭代次数最多为）。时间复杂度。

高级算法

问题分类

问题主要有验证判定问题、搜索问题、优化问题、计数问题。

0-1背包动态规划算法，暴力判定素数方法不属于多项式时间算法。

P问题：具有多项式时间算法的判定问题，可在多项式时间内求解。如素数判定、2-SAT、部分背包等。
NP问题：多项式时间内验证，不一定可解。
NPC问题：其他NP问题都可以在多项式时间内归约（符号）到的NP问题。如3-SAT、团、顶点覆盖、独立集、旅行商（TSP）等。NPC = P NP-Hard
NP-Hard问题：所有NP问题都能在多项式时间内归约到的问题，不一定是NP问题。

关系：P是NP的子集（P是否等于NP还无法判断，若相等则P等于NP等于NPC），NPC是NP的子集（NP问题不一定全能够在多项式时间内归约到P问题，取决于P是否与NP相等），NP-Hard包含NPC问题，可表示为下图。

dp[i][j]	1A	2B	3C	4D	5G	6H	7A
0	0	0	0	0	0	0	0
1A	1	1	1	1	1	1	1
2E	1	1	1	1	1	1	1
3D	1	1	1	2	2	2	2
4F	1	1	1	2	2	2	2
5H	1	1	1	2	2	3	3
6R	1	1	1	2	2	3	3

dp[i][j]	2a	3b	4c	5d
0	0	0	0	0
1a	1	0	0	0
2b	0	2	0	0
3c	0	0	3	0
4d	0	0	0	4
5e	0	0	0	0
6f	0	0	0	0
7g	0	0	0	0

dp[i][j]	0	1k	2i	3t	4t	5e	6n
0	0	1	2	3	4	5	6
1s	1	1	2	3	4	5	6
2i	2	2	1	2	3	4	5
3t	3	3	2	1	2	3	4
4t	4	4	3	2	1	2	3
5i	5	5	4	3	2	2	3
6n	6	6	5	4	3	3	2
7g	7	7	6	5	4	4	3

dp[i][j]	1A	2B	3C	4D	5G	6H	7A
0	0	0	0	0	0	0	0
1A	1	1	1	1	1	1	1
2E	1	1	1	1	1	1	1
3D	1	1	1	2	2	2	2
4F	1	1	1	2	2	2	2
5H	1	1	1	2	2	3	3
6R	1	1	1	2	2	3	3

dp[i][j]	2a	3b	4c	5d
0	0	0	0	0
1a	1	0	0	0
2b	0	2	0	0
3c	0	0	3	0
4d	0	0	0	4
5e	0	0	0	0
6f	0	0	0	0
7g	0	0	0	0

dp[i][j]	0	1k	2i	3t	4t	5e	6n
0	0	1	2	3	4	5	6
1s	1	1	2	3	4	5	6
2i	2	2	1	2	3	4	5
3t	3	3	2	1	2	3	4
4t	4	4	3	2	1	2	3
5i	5	5	4	3	2	2	3
6n	6	6	5	4	3	3	2
7g	7	7	6	5	4	4	3

基础知识

渐进符号

分析方法

和式求解

主定理法

分治算法

算法原理

经典问题

归并排序

最大子数组

逆序计数

快速排序

次序选择

动态规划

算法原理

经典问题

0-1背包

最大子数组

最长公共子序列

最长公共子串

最小编辑距离

贪心算法

算法原理

经典问题

部分背包

霍夫曼编码

活动选择

图算法

图的基本概念

图搜索算法

广度优先搜索

深度优先搜索

环路检测

拓扑排序

强连通分量

最小生成树

Prim

Kruskal

单源最短路径

Dijkstra

Bellman-Ford

点对最短路径

高级算法

问题分类

算法中英文表

dp[i][j]	1A	2B	3C	4D	5G	6H	7A
0	0	0	0	0	0	0	0
1A	1	1	1	1	1	1	1
2E	1	1	1	1	1	1	1
3D	1	1	1	2	2	2	2
4F	1	1	1	2	2	2	2
5H	1	1	1	2	2	3	3
6R	1	1	1	2	2	3	3

dp[i][j]	2a	3b	4c	5d
0	0	0	0	0
1a	1	0	0	0
2b	0	2	0	0
3c	0	0	3	0
4d	0	0	0	4
5e	0	0	0	0
6f	0	0	0	0
7g	0	0	0	0

dp[i][j]	0	1k	2i	3t	4t	5e	6n
0	0	1	2	3	4	5	6
1s	1	1	2	3	4	5	6
2i	2	2	1	2	3	4	5
3t	3	3	2	1	2	3	4
4t	4	4	3	2	1	2	3
5i	5	5	4	3	2	2	3
6n	6	6	5	4	3	3	2
7g	7	7	6	5	4	4	3