复杂度分析

时间复杂度

概念

公式：T(n) = O(f(n))；所有代码的执行时间T(n)与每行代码的执行次数n成正比。
反映的是代码执行时间随着数据规模增长的变化趋势。

分析技巧

(1) 只关注循环执行次数最多的一段代码。
(2) 加法法则：总复杂度等于量级最大的那段代码的复杂度。
(3) 乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积。

常见时间复杂度

O(n!) > O(2^n) > O(n^2) > O(nlogn) > O(n) > O(logn) > O(1)

细分

(1) 最好情况时间复杂度：最理想情况下，执行代码的时间复杂度。
(2) 最坏情况时间复杂度：最糟糕情况下，执行代码的时间复杂度。
(3) 平均情况时间复杂度：根据概率计算得出的加权平均时间复杂度（期望时间复杂度）。
(4) 均摊时间复杂度：通过摊还分析方法得到，可以将时间复杂度高的操作，平摊到其他时间复杂度较低的操作上，用于特殊场景（对于一个数据结构的一组连续操作中，大部分情况下时间复杂度很低，个别情况下时间复杂度较高，且操作前后连贯具有一定规律性）。

空间复杂度

概念

反映的是算法的存储空间与数据规模之间的增长关系。

常见空间复杂度

O(n^2) > O(n) > O(1)

算法

递归

满足条件

1、一个问题的解可以分解为几个子问题的解。
2、主问题和分解之后的子问题，除了数据规模不同，求解思路完全一样。
3、存在递归终止条件。

如何编写递归代码

1、写出递推公式。
2、找到终止条件。
3、关键在于找到如何将大问题分解成小问题的规律。

思考技巧

仅思考主问题和子问题之间的关系，不用关注子问题更下层的调用关系，不要试图用人脑去分解递归的每个步骤。

注意事项

1、避免递归深度过大导致堆栈溢出（空间复杂度高）。
2、避免重复计算（函数调用耗时多）。

优化技巧

尾递归：在函数返回的时候，调用函数自身，且return语句不包含表达式。这样，编译器或解释器可以对尾递归做优化，使递归本身无论调用多少次，都只占用一个栈帧，不会出现栈溢出的情况。

代码模板

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

void Recur(int level, int param) {
    // 递归终止条件
    if (level > MAX_LEVEL) {
        return;
    }
    
    // 当前层的处理逻辑
    
    // 进行递归调用
    Recur(level, param);
    
    // 清理当前层状态
}

排序

后续涉及的排序算法均以元素为数字的数组为例进行阐述。

1、排序算法的分析

1.1 基本操作
(1) 元素的比较。
(2) 元素的交换或移动。

1.2 执行效率
(1) 最好情况、最坏情况、平均情况时间复杂度。
(2) 考虑时间复杂度的系数、常数、低阶。
(3) 元素的比较次数和移动次数。

1.3 内存消耗
原地排序算法：指空间复杂度为 O(1) 的排序算法。

1.4 稳定性
待排序的序列中存在值相等的元素，经过排序后，如果相等元素之间原有的先后顺序不变，则排序算法称为稳定排序算法，否则称为不稳定排序算法。

1.5 额外概念
(1) 有序度：数据中具有有序关系的元素对的个数。
(2) 逆序度：数据中不具有有序关系的元素对的个数。
(3) 满有序度：完全有序的数据的有序度，值为 n*(n-1)/2。

2、冒泡排序

2.1 核心思想
每次只操作相邻的两个数据，若不满足关系，则将相邻元素交换。

2.2 实现思路
使用 2 个 for 循环，内部 for 循环每次执行完后，保证从数组尾部开始的元素是有序的，具体有序的元素的个数随着每次循环会增加。

2.3 时间复杂度
(1) 最好情况：O(n)；数组中的元素已有序，只需依次做比较操作。
(2) 最坏情况：O(n^2)；数组中的元素为倒序排列，要做 n 次冒泡操作。
(3) 平均情况：O(n^2)；满有序度 = n*(n-1)/2 = 有序度+逆序度；每交换一次，有序度+1，初始逆序度 = 总交换次数。

3、插入排序

3.1 核心思想
取“未排序区间”中的元素，在“已排序区间”中找到合适的位置将其插入（涉及数组元素的移动），并保证已排序区间中的元素一直有序，重复该过程，直到未排序区间为空为止。

3.2 实现思路
使用 2 个 for 循环，内部 for 循环执行完之后，保证从数组头部开始的元素是有序的，具体有序的元素的个数随着每次循环会增加。

3.3 时间复杂度
(1) 最好情况：O(n)；数组中的元素已有序，只需依次做比较操作。
(2) 最坏情况：O(n^2)；数组中的元素为倒序排列，需要大量移动数据。
(3) 平均情况：O(n^2)。

3.4 思考题：插入排序为何比冒泡排序更受欢迎？
(1) 冒泡排序的元素交换，会引入临时变量，进行 3 次赋值。
(2) 插入排序的元素移动，只进行 1 次赋值。

4、选择排序

4.1 核心思想
类似于插入排序，每次从未排序区间中找到最小的元素，放到已排序区间的末尾（涉及数组元素的交换）。

4.2 时间复杂度
(1) 最好情况：O(n^2)。
(2) 最坏情况：O(n^2)。
(3) 平均情况：O(n^2)。

5、归并排序

5.1 核心思想
分治：将数组从中间分为前后两部分，对前后两部分别进行排序，再将排序好的两部分合并在一起；利用递归技巧，对于拆分后的部分进行再次拆分的操作。

5.2 时间复杂度（通过递归思想分解时间复杂度的组成部分得出）
(1) 最好情况：O(nlogn)。
(2) 最坏情况：O(nlogn)。
(3) 平均情况：O(nlogn)。

5.3 空间复杂度
每次合并时临时开辟的空间在使用完之后会被立即释放，临时内存空间最大不会超过 n 个数据的大小，空间复杂度为 O(n)。

6、快速排序

6.1 核心思想
分治：选择数组中任意一个元素的位置作为分区点，遍历数组，将小于分区点元素的元素放在其左边，将大于分区点元素的元素放在其右边；利用递归技巧对于分区后的数据再次进行分区操作。

6.2 完成原地分区的技巧
使用数组元素的交换来避免递归分区过程中占用很多临时的内存空间，空间复杂度为 O(1)。

6.3 与归并排序的区别
(1) 归并排序：处理过程由下到上，子问题处理完后进行合并，一层一层往上。
(2) 快速排序：处理过程由上到下，先分区再处理子问题。

6.4 时间复杂度
(1) 最好情况：O(nlogn)。
(2) 最坏情况：O(n^2)。
(3) 平均情况：O(nlogn)。

6.5 特点
(1) 通用性好：覆盖场景广泛。
(2) 性能好：时间复杂度相对低；空间复杂度最低。

6.6 优化技巧
(1) 合理选择分区点：多数取中（取多个分布在区间全范围的值，取中间值）；随机（随机选择一个元素作为分区点）。
(2) 防止栈溢出：设置递归次数阈值；在堆上实现一个函数调用栈，模拟递归操作。

7、桶排序

7.1 核心思想
将要排序的数据分散到多个桶中，将每个桶里的数据单独进行排序，完成后，再把每个桶中的数据按照顺序取出，就组成了有序的数据。

7.2 应用场景
外部排序：数据存储在外部磁盘中，数据量较大，内存有限，无法将数据全部加载到内存中。

7.3 时间复杂度
O(n)：如果要排序的数据有 n 个，均匀分到 m 个桶内，每个桶里有 k = n/m 个元素。每个桶内使用快速排序，时间复杂度为 O(k * logk)。m 个桶的时间复杂度就是 O(m * k * logk)，就是 O(n * log(n/m))。当桶的个数接近数据个数 n 时，log(n/m) 就是一个非常小的常量，这时候桶排序的时间复杂度接近 O(n)。

8、计数排序

8.1 核心思想
一种特殊情况下的桶排序。若数据的最大值是 k，把数据划分成 k 个桶，每个桶内的数据值都是相同的，省掉了桶内排序的时间。借助处理过的桶数组（索引对应了数据值，元素为小于等于该索引值的数据的个数），利用元素值来确定当前数据值在排序后数组中的位置（取数据时需要从原始数据的最后一个元素开始往前遍历，以保证稳定性），来给原始数据排序。

8.2 应用场景
要排序的 n 个数据，数据范围并不大的时候；只能给非负整数排序，如果要排序的数据是其他类型的，要将其在不改变相对大小的情况下，转化为非负整数。

8.3 时间复杂度
O(n)。

9、基数排序

9.1 核心思想
处理要排序的数据，位数不够的在后面补“0”。

9.2 应用场景
被排序的数据，可以分割出独立的“位”来比较，位与位之间有递进关系，每一位的数据范围不能太大。

9.3 时间复杂度
O(n)。

10、堆排序

10.1 核心思想
借助“二叉堆”数据结构实现的排序算法。

10.2 准备工作（建堆）
在数组上，不借助其他数组，原地建堆。
(1) 思路1：借助插入元素的思路，假设起初堆中只包含一个数据（下标为 1 的数据），然后调用插入操作，将下标从 2 到 n 的数据依次插入到堆中。这样就将包含 n 个数据的数组，组织成了堆。
(2) 思路2：从后往前处理数据，每个数据从上往下进行堆化（针对下标 1 ~ n/2 的数据进行堆化，在完全二叉树中，下标 n/2+1 ~ n 的数据都是叶子节点）。

10.3 实现思路
类似于堆顶元素的删除，当堆顶元素移除之后，把下标为 n 的元素放到堆顶，然后再通过堆化的方法，将剩下的 n−1 个元素重新构建成堆。堆化完成之后，我们再取堆顶的元素，放到下标是 n−1 的位置，一直重复这个过程，直到最后堆中只剩下标为 1 的一个元素，就完成了排序。

10.4 时间复杂度
建堆的时间复杂度为 O(n)，排序的时间复杂度为 O(nlogn)，因此堆排序整体的时间复杂度为 O(nlogn)。

10.5 思考：为什么快速排序比堆排序性能好？
(1) 快速排序的数据访问是顺序的，局部的；而堆排序的数据访问不是顺序的，是跳着的，对于CPU缓存不友好。
(2) 对于同样的数据，在排序过程中，堆排序算法的数据交换次数要多于快速排序。

查找

1、二分查找

1.1 核心思想
每次通过与区间的中间元素进行对比，将查找范围缩小一半，直到查到指定元素或区间被缩小为 0。

1.2 应用场景
(1) 数据必须是有序的。
(2) 数据存在上下界。
(3) 数据存储在顺序表结构中，元素能够通过下标进行随机访问。
(4) 数据量适中（太小的话时间上相比顺序遍历没有优势，太大的话对于内存要求过高）。

1.3 变形问题
常用于有序集合（从小到大排列）中存在重复元素的场景。
注意细节：终止条件、区间上下边界更新方法、返回值选择。
(1) 查找第一个值等于指定值的元素。
思路：查找到给定值的时候，判断当前位置的前一个元素的值是否也为给定值。
(2) 查找最后一个值等于给定值的元素。
思路：与查找第一个符合条件的元素相似，查找到指定值的时候，判断当前位置的后一个元素的值是否也为指定值。
(3) 查找第一个值大于等于给定值的元素。
思路：每当查找到给定值的位置，判断其前一个元素的值是否小于给定值。
(4) 查找最后一个值小于等于给定值的元素。
思路：每当查找到给定值的位置，判断其后一个元素值是否大于给定值。

1.4 时间复杂度
O(logn)。

1.5 代码模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

// 假设数组中的元素是升序排列的
int binarySearch(vector<int> numArray, int target) {
    int index = -1;
    
    int left = 0;
    int right = numArray.size() - 1;
    int mid = (left + right) / 2;
    while (left <= right) {
        if (numArray[mid] == target) {
            index = mid;
            
            break; 
        } else if (numArray[mid] > target) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
        
        mid = (left + right) / 2;
    }
    
    return index;
}

哈希算法

概念

将任意长度的二进制值串映射为固定长度的二进制值串（哈希值），其映射规则称为哈希算法。

特点

1、从哈希值不能反向推导出原始数据。
2、对输入数据非常敏感，即使只改变 1 个 bit，得到的哈希值也会大不相同。
3、针对不同的原始数据，哈希值相同的概率要非常小。
4、执行要高效，对于较长的文本，也要能够快速计算出哈希值。

应用场景

1、安全加密
常见加密算法：MD5、SHA、DES、AES。

2、唯一标识
例：在海量的图库中搜索图片，使用图片的一些信息生成唯一标识。

3、数据校验
例：针对从网络上下载的文件进行校验。

4、散列函数
例：散列表中使用到的散列函数。

5、负载均衡
例：实现一个会话粘滞的负载均衡算法。对客户端IP地址或会话ID计算哈希值，将取得的哈希值与服务器列表的大小进行取模运算，最终得到的值就是需要路由的服务器编号，可以把同一个IP过来的所有请求，都路由到同一个后端服务器上。

6、数据分片
例：统计“搜索关键词”出现的次数。从搜索记录的日志文件中，依次独处每个搜索关键词，通过哈希算法计算得到哈希值，跟机器数量n取模，得到机器编号，将同一个搜索关键词分配到同一台机器上，最后将所有机器上的结果合并得到所需内容。

7、分布式存储
例：使用一致性哈希算法，可以在多台缓存机器集群中加入一个新机器时，不需要做大量的数据搬移。

搜索

1、广度优先搜索（BFS）

假设使用邻接表来存储无向图，V表示顶点的个数，E表示边的个数。

1.1 核心思想
(1) 每个节点都要访问一次，而且仅访问一次。
(2) 先查找离起始顶点最近的，然后是次近的，依次往外搜索。

1.2 实现思路
(1) 记录顶点的访问状态，避免重复访问。
(2) 用队列存储已被访问的但是相连顶点未被访问的顶点。
(3) 用数组来反向存储路径，下标为x的元素的值是第x个顶点的前驱顶点的编号。

1.3 时间复杂度
因在连通图中，E一定大于等于(V-1)，因此时间复杂度可简写为O(E)。

1.4 空间复杂度
用于存储顶点和顶点状态的数组和队列大小不会超过顶点个数，因此空间复杂度为O(V)。

1.5 代码模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

map<int, int> visited = {};
int targetValue;

void bfs(Node *root) {
    // 终止条件
    if (!root) {
        return;
    }
    
    queue<Node *> nodeQueue;
    nodeQueue.push(root);
    
    while (!nodeQueue.empty()) {
        // 使用队列来保存节点
        Node *node = nodeQueue.front();
        nodeQueue.pop();
        
        // 判断节点是否已访问
        if (visited.count(node->val)) {
            continue;
        }
        visited[node->val] = 1;
        
        // 处理当前节点
        if (node->val == targetValue) {
            // code
        }
        
        // 将当前节点的孩子节点加入队列
        for (int i = 0; i < node->childrenArray.size(); i++) {
            nodeQueue.push(node->childrenArray[i]);
        }
    }
}

2、深度优先搜索（DFS）

假设使用邻接表来存储无向图，V表示顶点的个数，E表示边的个数。

2.1 核心思想
(1) 每个节点都要访问一次，而且仅访问一次。
(2) 从起始顶点开始，遍历各个分支进行查找，没有结果时返回上一个顶点走其他分支。

2.2 实现思路
(1) 使用递归思路进行实现。
(2) 记录顶点的访问状态，避免重复访问。
(3) 用数组来反向存储路径，下标为x的元素的值是第x个顶点的前驱顶点的编号。

2.3 时间复杂度
每条边最多会被访问2次，因此时间复杂度为O(E)。

2.4 空间复杂度
递归调用栈的最大深度不会超过顶点的个数，因此空间复杂度为O(V)。

2.5 代码模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

map<int, int> visited = {};
int targetValue;

void dfs(Node *root) {
    // 终止条件
    if (!root) {
        return;
    }
    
    // 判断节点是否已访问
    if (visited.count(root->val)) {
        return;
    }
    visited[root->val] = 1;
    
    // 处理当前节点
    if (root->val == targetValue) {
        // code
    }
    
    // 进行不同分支节点的遍历
    for (int i = 0; i < root->childrenArray.size(); i++) {
        dfs(root->children[i]);
    }
}

3、双向 BFS

3.1 核心思想
从头部和尾部交替（不严格）向中间进行广度优先搜索，直到找到目标为止。

3.2 代码模板
暂无，待补充。

4、启发式搜索

4.1 核心思想
通过估价函数，每次遍历时根据优先级找到最有可能的节点，然后进行搜索，直到找到目标为止。

4.2 代码模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

class Node {
public:
    int x;
    int y;
    bool operator< (const Node &A) {
        //
    }
};

void generate_related_nodes(Node &node) {
    //
}

void process(Node &node) {
    //
}

void AstarSearch(vector<vector<int>>& graph, Node& start, Node& end) {
    vector<vector<bool>> visited(graph.size(), vector<bool>(graph[0].size(), false));
    priority_queue<Node> q;
    q.push(start);
    while (!q.empty()) {
        Node cur = q.top();
        q.pop();
        
        visited[cur.x][cur.y] = true;
        
        process(node);
        
        vector<Node> nodes = generate_related_nodes(node);
        
        for (auto node : nodes) {
            if (!visited[node.x][node.y]) {
                q.push(node);
            }
        }
    }
}

字符串匹配

场景：在字符串 A 中查找字符串 B。
主串：字符串 A，长度为 n。
模式串：字符串 B，长度为 m。

1、BF算法

BF：Brute Force，暴力匹配算法，也可称朴素匹配算法。

1.1 核心思想
在主串中，检查起始位置分别为 0、1、2…(n-m) 且长度为 m 的 n-m+1 个子串，看是否有跟模式串匹配的字符串。

1.2 时间复杂度
每次要对比 m 个字符，总共对比 n-m+1 次，所以整体的时间复杂度为 O(n*m)。

2、RK算法

RK：Rabin-Karp，由两位发明者的命名而来。

2.1 核心思想
使用哈希算法对主串中的 n-m+1 个子串分别求哈希值，然后逐个与模式串的哈希值进行对比，若哈希值相同，则说明匹配了。

2.2 哈希算法设计思路
假设字符集只包含 K 个字符。
(1) 用一个 K 进制数来表示一个子串，将 K 进制数转换成 10 进制数，作为子串的哈希值，这样的算法不会出现哈希值冲突。
(2) 该种哈希算法有个特点：相邻子串的哈希值的计算公式有一定关系，可以通过前一个子串的哈希值快速算出下一个子串的哈希值。
(3) 为了哈希值能落在整数范围内，可以允许哈希冲突，在冲突时，逐字符比较一下子串和模式串即可，整体的效率还是会比BF算法高。

2.3 时间复杂度
计算子串哈希值的时间复杂度为 O(n)，匹配时哈希值对比的时间复杂度为 O(1)，总共匹配 n-m+1 次，所以整体的时间复杂度为 O(n)。

3、BM算法

BM：Boyer-Moore。

3.1 核心思想
寻找模式串在主串中移动的规律，减少不必要的字符比较，提升模式串匹配的效率。

3.2 实现思路
“坏字符规则”和好前缀规则“结合使用。
(1) 坏字符规则：
当发生不匹配的时候，我们把坏字符对应的模式串中的字符的下标记作 si，坏字符在模式串中的下标记作 xi。如果坏字符在模式串中存在，xi 就是坏字符在模式串中的下标，通常取模式串中最后一个坏字符的下标；如果不存在，xi 记作 -1。模式串往后移动的位数就等于 si-xi。
(2) 好后缀规则：
假设主串中有个子串与模式串末尾的子串匹配，记为 {u}。
a) 若在模式串中找到了另一个与 {u} 匹配的子串 {u1}，则将模式串移动到 {u1} 与 {u} 对齐的位置。
b) 若在模式串的其他位置找不到与 {u} 匹配的子串，则判断 {u} 的后缀中是否有与模式串的前缀匹配的子串；若存在，则将模式串移动到前缀子串与 {u} 的后缀子串匹配的位置；若不存在，将模式串移动到 {u} 的后面。
(3) 规则的使用
a) 分别计算好后缀和坏字符往后滑动的位数，然后取两个数中最大的，作为模式串往后滑动的位数，可以有效避免坏字符规则时可能出现的移动位数为负数的情况。
b) 坏字符规则比较消耗内存，可以只使用好后缀规则。

3.3 应用场景
适合模式串较短的场景（比如文本编辑器中的字符串搜索）。

4、KMP算法

KMP：Knuth Morris Pratt，由三位作者的命名而来。

4.1 核心思想
寻找模式串在主串中移动的规律，减少不必要的字符比较，提升模式串匹配的效率（相比于BM算法，移动时只关注模式串前缀子串与主串的匹配）。

4.2 实现思路
(1) 每次匹配失败后模式串向后移动的距离仅与模式串本身有关。因为当匹配到失败字符时，模式串当前字符之前的子串肯定与主串中的子串相同。因此要先找到模式串中出错字符前的子串中的最长可匹配的前缀字符串和后缀字符串，这 2 个字符串的距离之差，就是模式串要移动的距离。
(2) 使用 next 数组，下标是模式串中每个前缀字符串的结尾字符的下标，值是该下标对应前缀字符串中的最长可匹配前缀字符串结尾字符的下标，使用下标 -1 表示不存在的情况。

4.3 next数组的构造原理
待研究。

4.4 应用场景
似乎适合所有单个字符串匹配的场景？待研究。

5、Trie树

5.1 概念
trie 树是一种专门处理字符串匹配的数据结构，用来解决在一组字符串集合中快速查找某个字符串的问题。其本质是利用字符串之间的公共前缀，降低查找时间。
(1) 节点本身不存储完整单词。
(2) 从根节点到某一节点，路径上经过的字符连接起来，就是该节点对应的字符串。
(3) 所有节点的子节点路径代表的字符都不相同。

5.2 存储方式
(1) 假设字符串中只有从 a 到 z 这 26 个小写字母，每个节点的数据结构中维护一个当前节点的字符数据和一个大小为 26 的数组。在数组中下标为 0 的位置，存储指向子节点 a 的指针，下标为 1 的位置存储指向子节点 b 的指针，以此类推，下标为 25 的位置，存储的是指向的子节点 z 的指针。如果某个字符的子节点不存在，就在对应的下标的位置存储 NULL。
(2) 默认情况下使用的数组会很浪费内存空间，可以替换成散列表、跳表、红黑树等数据结构。

5.3 时间复杂度
(1) 构建 Trie 树：需要遍历所有字符串，因此时间复杂度与构建时用的所有字符串总长度 n 有关，为 O(n)。
(2) 查找字符串：字符串长度为 k，最多对比 k 个节点即可得出结果，因此时间复杂度为 O(k)。

5.4 应用场景
适合查找前缀匹配的字符串（比如输入关键词跳出联想结果、对输入内容进行自动补全或修正）。

6、AC自动机

AC：Aho-Corasick。

6.1 核心思想
在 Trie 树之上，加了类似 KMP 算法的 next 数组，此处的 next 数组是构建在树上的。

6.2 实现思路
(1) 在树的每个节点保存失败指针，对应到 KMP 算法中 next 数组的值。
(2) 失败指针的构造与 KMP 算法中 next 数组的构造原理类似。

6.3 应用场景
适合在大量文本中进行多个模式串的匹配查找。

分治算法

核心思想

将原问题划分成 n 个规模较小，并且结构与原问题相似的子问题，解决这些子问题，然后再合并其结果，通常使用递归进行实现。

实战分析

1、归并排序、快速排序。
2、二维平面上有 n 个点，如何快速计算出两个距离最近的点对？
3、有两个 n*n 的矩阵 A，B，如何快速求解两个矩阵的乘积 C=A*B？
4、MapReduce模型。

代码模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

vector<auto> DivideAndConquer(auto problem, auto param1, auto param2, ...) {
    // 递归终止条件
    if (problem == NULL) {
        return;
    }
    
    // 当前层的处理逻辑
    auto data = PrepareData(problem);
    auto subProblems = SplitProblem(problem, data);
    
    // 进行递归调用
    vector<auto> subResult1 = DivideAndConquer(subProblems[0], p1, p2, ...);
    vector<auto> subResult2 = DivideAndConquer(subProblems[1], p1, p2, ...);
    vector<auto> subResult3 = DivideAndConquer(subProblems[2], p1, p2, ...);
    
    // 合并所有结果
    auto result = MergeResult(subResult1, subResult2, subResult3, ...);
    
    // 清理当前层状态
}

回溯算法

核心思想

把问题求解的过程分为多个阶段，面对分支时先随意走一个分支，当发现分支走不通的时候（不符合期望的解），就回退到上一个岔路口，另选一个分支继续走，使用递归进行实现。

实战分析

1、八皇后问题：有一个 8x8 的棋盘，希望往里放 8 个棋子（皇后），每个棋子所在的行、列、对角线都不能有另一个棋子。
2、0-1 背包问题。
3、正则表达式与文本的匹配。

贪心算法

核心思想

1、问题能够分解成子问题来解决，子问题的最优解能递推到最终问题的最优解。
2、在每一步选择中都采取当前状态下的最优解，从而希望实现全局最优。
3、与动态规划的不同点在于，贪心算法对于每个子问题的解决方案都做出选择，不能回退；而动态规划会保存以前的运算结果，并根据以前的结果对当前进行选择，可以回退。

实战分析

1、分糖果：现在有 m 个糖果和 n 个孩子，要把糖果分给这些孩子吃，但是糖果少，孩子多（m<n），所以糖果只能分配给一部分孩子。如何分配糖果，能尽可能满足最多数量的孩子？
2、凑钱：现在有 1 元、2 元、5 元、10 元、20 元、50 元、100 元这些面额的纸币，它们的张数分别是 c1、c2、c5、c10、c20、c50、c100。现在要用这些钱来支付 K 元，最少要用多少张纸币？
3、区间覆盖：现在有 n 个区间，区间的起始端点和结束端点分别是 [l1, r1]，[l2, r2]，[l3, r3]，……，[ln, rn]。从这 n 个区间中选出一部分区间，这部分区间满足两两不相交（端点相交的情况不算相交），最多能选出多少个区间？

动态规划

动态规划 = 分治 + 最优子结构

核心思想

一个模型
多阶段决策最优解模型。解决问题的过程，需要经历多个决策阶段。每个决策阶段都对应着一组状态。然后我们寻找一组决策序列，经过这组决策序列，能够产生最终期望求解的最优值。

三个特征
(1) 最优子结构：问题的最优解包含了子问题的最优解，反之，可以通过子问题的最优解推导出问题的最优解；中途可以淘汰次优解。
(2) 无后效性：在推导后面阶段的状态的时候，只关心前面阶段的状态值，无需关心前面状态是如何推导而来的；前一阶段的状态不受后面阶段的决策影响。
(3) 重复子问题：不同的决策序列，到达某个相同的阶段时，可能会产生重复的状态。

实现思路

1、状态转移表法：状态表通常为二维数组；按照决策过程，通过不断状态递推演进，将状态表填好，再将填表的过程翻译成代码。
2、状态转移方程法：根据最优子结构，写出递归公式，再翻译成代码。

编程技巧

1、寻找问题的重复性（打破自己的思维惯性，形成机器思维）。
2、定义状态（理解复杂逻辑的关键）。
3、列出 DP 方程。

代码模板

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

// 定义状态（假设是二维的）
dp[][];

for (int i = 0; i < m; i++) {
    for (int j = 0; j < n; j++) {
        // 状态转移方程
        dp[i][j] = _Function(dp[i'][j']);
    }
}

// 返回反映最终情况的结果
return dp[m'][n'];