算法设计与分析（89讲）
掌握五大算法策略，学会自己设计算法
课程介绍
这门课共10章89讲，带你系统掌握递归与分治、动态规划、贪心、回溯、分支限界五大算法设计策略，并延伸到概率算法、NP完全理论与高级优化技巧。课程采用思路推导式板书教学，不直接给答案，而是带你一步步推导状态转移方程、证明正确性并分析复杂度，精讲三十余个经典算法问题。学完你将建立算法设计的系统思维，面对新问题知道如何分析、求解与优化，适合在校学习、考研、竞赛和技术面试备考。
学完你将能够
- 掌握分治、动态规划等五大设计策略
- 独立推导动态规划的状态转移方程
- 求解并分析三十余个经典算法问题
- 证明贪心算法的正确性与适用条件
- 运用回溯与分支限界搜索组合问题解
- 理解P、NP与NP完全理论的关系
课程大纲
第1章 引论 5 个要点
- 算法的定义与五大特性
- 伪代码与抽象数据类型
- 算法描述语言与递归描述
- 渐进记号与时间空间复杂度
- 最坏、最好与平均情况分析
第2章 递归与分治 6 个要点
- 递归概念、两要素与调用栈
- 阶乘、汉诺塔与整数划分实例
- 分解、求解、合并三步分治法
- 二分搜索与大整数乘法
- 归并排序、快速排序与线性时间选择
- 二维平面最接近点对问题
第3章 动态规划 6 个要点
- 最优子结构与重叠子问题
- 矩阵连乘与状态转移方程
- 自底向上填表与备忘录方法
- 回溯构造具体最优方案
- 背包问题与流水作业调度
- 滚动数组空间优化与四边形不等式入门
第4章 贪心算法 5 个要点
- 活动安排与区间调度问题
- 贪心选择性质与最优子结构
- 迪杰斯特拉单源最短路径
- 普里姆与克鲁斯卡尔最小生成树
- 拟阵理论与正确性证明框架
第5章 回溯法 6 个要点
- 子集树、排列树与解空间
- 深度优先搜索与剪枝框架
- 装载问题与0-1背包回溯
- n后问题与图的着色问题
- 批处理调度与符号三角形
- 回溯效率分析与优化策略
第6章 分支限界法 5 个要点
- 队列式与优先队列式分支限界
- 与回溯法的区别及适用场景
- 单源最短路径与布线问题
- 背包问题与最大团的界函数设计
- 旅行商问题与作业调度求解
第7章 概率算法 5 个要点
- 随机化思想与四类概率算法
- 蒙特卡洛方法计算定积分
- 舍伍德算法消除最坏情况
- 跳跃表概率数据结构
- 拉斯维加斯与蒙特卡洛算法对比
第8章 NP问题 6 个要点
- P类与NP类问题的定义
- 多项式时间归约与NP完全性
- 布尔可满足性问题与库克定理
- 团问题的NP完全性证明
- 近似算法与近似比分析
- 旅行商问题的近似求解
第9章 子串 5 个要点
- 单模式与多模式匹配问题
- AC自动机与失败指针
- 后缀数组的倍增构造法
- 后缀数组的线性时间分治构造
- 编辑距离与最长公共子序列
第10章 算法优化 6 个要点
- 朴素算法的复杂度瓶颈
- 分治优化与决策单调性
- 四边形不等式优化动态规划
- 带权区间最短路优化实例
- 迭代加深搜索与启发函数剪枝
- 对称性、可行性等高级剪枝