编辑推荐
一本囊括基本算法知识的详解指南，详细讲解算法理念，展现算法本质。
内容简介
“算法详解”系列图书共有4卷，本书是第3卷——贪心算法和动态规划。其中贪心算法主要包括调度、最小生成树、聚类、哈夫曼编码等，动态规划主要包括背包、序列比对、最短路径、最佳搜索树等。本书的每一章均有小测验和章末习题，这将为读者的自我检查以及进一步学习提供方便。 本书作者提供丰富而实用的资源，能够帮助读者提升算法思维能力。本书适合计算机专业的高校教师和学生、想要培养和训练算法思维、计算思维的IT专业人士，以及面试官和正在准备面试的应聘者阅读、参考。
作者简介
作者蒂姆·拉夫加登，哥伦比亚大学计算机科学系的教授，之前曾任教于斯坦福大学计算机科学系，他从2004年开始教授和研究算法。
章节目录
版权信息
内容提要
前言
服务与支持
第1章 贪心算法概述
1.1 贪心算法设计范例
1.1.1 算法设计范例
1.1.2 贪心算法设计范例的特性
1.2 一个调度问题
1.2.1 问题的设定
1.2.2 竞争时间
1.2.3 目标函数
1.2.4 小测验1.1的答案
1.3 开发一种贪心算法
1.3.1 两种特殊情况
1.3.2 贪心算法之间的竞争
1.3.3 小测验1.2～1.3的答案
1.4 正确性证明
1.4.1 没有平局时的情况：高层计划
1.4.2 在相邻逆序对中交换作业
1.4.3 成本收益分析
1.4.4 处理平局的情况
1.4.5 小测验1.4～1.5的答案
1.5 本章要点
1.6 章末习题
编程题
第2章 哈夫曼编码
2.1 编码
2.1.1 固定长度的二进制编码
2.1.2 可变长度的编码
2.1.3 非前缀编码
2.1.4 非前缀编码的优点
2.1.5 问题定义
2.1.6 小测验2.1～2.2的答案
2.2 编码和树
2.2.1 3个例子
2.2.2 什么样的树表示非前缀编码
2.2.3 问题定义（精练版）
2.3 哈夫曼的贪心算法
2.3.1 通过连续的归并创建树
2.3.2 哈夫曼的贪心准则
2.3.3 伪码
2.3.4 例子
2.3.5 一个更复杂的例子
2.3.6 运行时间
2.3.7 小测验2.3的答案
*2.4 正确性证明
2.4.1 高层计划
2.4.2 细节
2.5 本章要点
2.6 章末习题
挑战题
编程题
第3章 最小生成树
3.1 问题定义
3.1.1 图
3.1.2 生成树
3.1.3 小测验3.1的答案
3.2 Prim算法
3.2.1 例子
3.2.2 伪码
3.2.3 简单的实现
*3.3 通过堆提升Prim算法的速度
3.3.1 探求接近线性的运行时间
3.3.2 堆数据结构
3.3.3 如何在Prim算法中使用堆
3.3.4 基于堆的实现的伪码
3.3.5 运行时间分析
3.3.6 小测验3.3的答案
*3.4 Prim算法：正确性证明
3.4.1 最小瓶颈属性
3.4.2 生成树的一些有趣结论
3.4.3 定理3.4（MBP意味着MST）的证明
3.4.4 综合运用
3.5 Kruskal算法
3.5.1 例子
3.5.2 Kruskal算法的伪码
3.5.3 Kruskal算法的简单实现
*3.6 通过合并查找对Kruskal算法进行加速
3.6.1 合并查找数据结构
3.6.2 基于合并查找的实现的伪码
3.6.3 基于合并查找的实现的运行时间分析
3.6.4 合并查找的快速有余而严谨不足的实现：父图
3.6.5 小测验3.5～3.7的答案
*3.7 Kruskal算法的正确性证明
3.8 应用：单链集群
3.8.1 集群
3.8.2 自底向上的集群
3.9 本章要点
3.10 章末习题
挑战题
编程题
第4章 动态规划概述
4.1 加权独立集合问题
4.1.1 问题定义
4.1.2 自然的贪心算法失败了
4.1.3 分治算法可行吗
4.1.4 小测验4.1～4.2的答案
4.2 路径图的WIS问题的线性时间算法
4.2.1 最优子结构和推导公式
4.2.2 一种不成熟的递归方法
4.2.3 使用缓存的递归算法
4.2.4 一种迭代式的自底向上的实现
4.2.5 小测验4.3～4.4的答案
4.3 一种重建算法
4.4 动态规划的原则
4.4.1 3个步骤的配方
4.4.2 子问题的期望属性
4.4.3 一个可重复的思维过程
4.4.4 动态规划和分治算法的区别
4.4.5 为什么叫“动态规划”
4.5 背包问题
4.5.1 问题定义
4.5.2 最优子结构和推导公式
4.5.3 子问题
4.5.4 一种动态规划算法
4.5.5 例子
4.5.6 重建
4.5.7 小测验4.5～4.6的答案
4.6 本章要点
4.7 章末习题
挑战题
编程题
第5章 高级动态规划
5.1 序列对齐
5.1.1 驱动力
5.1.2 问题定义
5.1.3 最优子结构
5.1.4 推导公式
5.1.5 子问题
5.1.6 一种动态规划算法
5.1.7 重新构建
5.1.8 小测验5.1～5.3的答案
*5.2 最优二叉搜索树
5.2.1 二叉搜索树回顾
5.2.2 平均搜索时间
5.2.3 问题定义
5.2.4 最优子结构
5.2.5 推导公式
5.2.6 子问题
5.2.7 一种动态规划算法
5.2.8 改善运行时间
5.2.9 小测验5.4～5.5的答案
5.3 本章要点
5.4 章末习题
挑战题
编程题
第6章 再论最短路径算法
6.1 边长可能为负的最短路径
6.1.1 单源最短路径问题
6.1.2 负环
6.1.3 小测验6.1的答案
6.2 Bellman-Ford算法
6.2.1 子问题
6.2.2 最优子结构
6.2.3 推导公式
6.2.4 什么时候应该停止
6.2.5 伪码
6.2.6 Bellman-Ford算法的例子
6.2.7 Bellman-Ford算法的运行时间
6.2.8 Internet路由
6.2.9 小测验6.2～6.3的答案
6.3 所有顶点对的最短路径问题
6.3.1 问题定义
6.3.2 简化为单源最短路径
6.3.3 小测验6.4的答案
6.4 Floyd-Warshall算法
6.4.1 子问题
6.4.2 最优子结构
6.4.3 伪码
6.4.4 检测负环
6.4.5 Floyd-Warshall算法的总结和开放性问题
6.4.6 小测验6.5～6.6的答案
6.5 本章要点
6.6 章末习题
挑战题
编程题
附录 章末习题答案节选
后记 算法设计工作指南
算法详解（卷3）：贪心算法和动态规划是2023年由人民邮电出版社出版,作者[美] 蒂姆·拉夫加登。
得书感谢您对《算法详解（卷3）：贪心算法和动态规划》关注和支持，如本书内容有不良信息或侵权等情形的，请联系本网站。
