PyAlgo

算法设计与分析

前言

学科地位：

主讲教师	学分配额	学科类别
段博佳	3	自发课

成绩组成：

平时（5次作业+签到）	期末（书本+讲义）
60%	40%

教材情况：

课程名称	选用教材	版次	作者	出版社	ISBN号
算法设计与分析	《算法设计与分析(python版)》	1	王秋芬	清华大学出版社	978-7-302-57072-1

一、贪心

Dijkstra、Prim、Kruskal、Huffman

二、分治

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

三、动规

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

四、深搜

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

考后碎碎念

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

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

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