算法设计与分析

一、贪心

Dijkstra、Prim、Kruskal、Huffman

二、分治

二分、归并、快排（第 k 个数）

三、动规

• 区间dp：矩阵连乘
• 网格图dp：LCS
• 背包：完全背包、多重背包

四、深搜

• 排列树：TSP、图染色、调度、n 皇后
• 子集树：01背包

考后碎碎念

考的中规中矩，但是忘带修正带导致卷面一坨hh。按照试卷顺序罗列一下：表达式树、大根堆、Dijkstra、图染色、第 k 个数、Kruskal、完全背包。

试卷一看就是 wq 出的，但还是用 python 写的代码。有一说一这次考试还加深了我对快排的理解，尤其是在让我给出分治后的序列时hh。硬要按照上面四个标签分类的话大概就是：

• 贪心：Dijkstra、Kruskal
• 分治：第 k 个数
• 动规：完全背包
• 深搜：表达式树、大根堆、图染色