【读书笔记】数据结构与算法之美 第10章 贪心、分治、回溯和动态规划
《数据结构与算法之美》，王争 著
标签：数据结构、算法
第10章 贪心、分治、回溯和动态规划
一、贪心算法
这一部分介绍了
如何理解贪心算法
贪心算法的应用示例（分糖果、最短服务时间、区间覆盖）
如何利用贪心算法实现霍夫曼编码
笔记：如何贪心，贪心模型是最关键的。严禁的证明贪心算法能得到最优解并不是一件容易的事情
二、分治算法
这一部分介绍了
如何理解分治算法
分治算法的应用示例（归并排序）
分治算法在大数据处理中的应用
大规模计算框架MapReduce中的分治思想
三、回溯算法
这一部分介绍了
如何理解回溯算法
八皇后问题
0-1背包问题
正则表达式匹配问题
笔记：回溯算法思想非常简单，但应用广泛，除了深度优先搜索算法，正则表达式匹配、编译原理中的语法分析等，还有很多经典数学问题，如数独、八皇后、0-1背包、图的着色、旅行商、求全排列等。大部分情况下，回溯可用来解决广义的搜索问题，也就是从一组可能的解中选出一个满足要求的解。回溯算法非常适合用递归来实现，在实现的过程中，剪枝操作是提高搜索效率的一种技巧。
四、初始动态规划
这一部分介绍了
动态规划的学习路线
利用动态规划解决0-1背包问题
0-1背包问题的升级版
如何巧妙解决双11购物是的凑单问题
五、动态规划理论
这一部分介绍了
一个模型和三个特征理论介绍
一个模型和三个特征的应用示例
动态规划的两种解题方法
六、动态规划实战：如何实现搜索引擎中的拼写纠错功能
这一部分介绍了
如何量化两个字符串的相似度
如何通过编程计算莱文斯坦距离
如何通过编程计算最长公共子串长度
本章笔记：贪心、分治、回溯和动态规划是经典的算法思想，是指导算法设计的原理，原理解释起来都很简单，但是要真正掌握并能灵活应用，并不是一件容易的事情，读者只有先学习算法设计思想，结合具体的问题，通过应用这些算法思想解决问题，才能不断提升算法设计能力水平。
无数优秀的算法、软件、系统、框架等设计思想源自基础数据结构和算法，这本身就是数据结构和算法的魅力，也是为什么在学习计算机的基础阶段要好好学习数据结构和算法的原因。
