《算法详解（卷3）贪心算法和动态规划》贪心算法与动态规划详解

本书介绍两个基本的算法设计范例，并提供一些相关的案例。

贪心算法及其应用

贪心算法通过一系列短视和不可逆的决策序列来解决问题。对于很多问题而言，设计一种具有“炫目”速度的贪心算法是非常容易的。然而，贪心算法的正确性并不能保证。但是，本书将讨论一些重量级的应用，它们不受这个规则的限制。这些应用包括调度问题、最优压缩以及图的最小生成树。

动态规划算法及其应用

动态规划算法通过严密的算法研究获得了很多好处，这些好处很少能够与其他方法相提并论。有一些问题是无法通过其他更简单的方法解决的，只有通过大量实践才能完善。本书的动态规划训练将涵盖这种编程范例的一些重要应用，包括背包问题、Needleman-Wunsch基因序列对齐算法、克努特的最优二叉搜索树算法以及贝尔曼-福特和弗洛伊德-华尔沙尔的最短路径算法。

本书内容的详细介绍可以在每章的“本章要点”中找到，该部分对每章的内容进行了总结，特别是那些重要的概念。在“后记：算法设计工作指南”中，我们对如何将贪心算法和动态规划算法应用于更大的算法场景进行了概述。

本书还提供了一些难度较高的章节，其标题带有“*”。对于时间紧张的读者，在第一遍阅读时可以跳过这些内容，这不会影响对本书内容的连续性。

“算法详解”系列的其他几卷涵盖了以下主题：

• 卷1：讨论了渐进性表示法（大O表示法和相关表示法）、分治算法和主方法，随机化的快速排序及其分析，以及线性时间的选择算法。
• 卷2：重点讨论了数据结构（堆、平衡搜索树、散列表、布隆过滤器）、图的基本单元（宽度优先搜索、深度优先搜索、连通性、最短路径）以及它们的应用（从去除重复项到社交网络分析）。
• 卷4：介绍了NP完整性及其对算法设计师的意义，还讨论了处理难解计算问题的一些策略，包括对试探法和局部搜索的分析。

本书的读者可以从中获得以下收益：

成为更优秀的程序员

读者将学习一些高效处理数据的“炫目”子程序以及一些实用的数据结构，这些子程序和数据结构可以直接应用于读者自己的程序中。理解和应用这些知识将扩展读者的编程知识范围，并提高读者的编程技术水平。读者还将学习基本的算法设计范例，这些范例与许多不同领域的不同问题密切相关，并且可以读者将有大量的实践机会来描述和推导算法。通过这样的分析，读者将对本书中介绍的特定算法和数据结构有深刻的理解。读者还将掌握一些实用的数学技巧，这些技巧广泛应用于算法分析中。

培养算法思维

学习算法之后，我们会发现几乎无处不在都有它们的踪影。无论是在坐电梯、观察鸟群，还是在管理投资组合，甚至是在观察婴儿的认知，算法思维都与我们息息相关。算法思维在计算机科学以外的领域，包括生物学、统计学和经济学等，变得越来越实用。

融入计算机科学家的圈子

研究算法就像观看计算机科学发展的精彩剪辑。当参加计算机科学界的社交活动时，如果有人讲述关于Dijkstra算法的笑话，你将不会感到自己被排除在外。在阅读本系列图书之后，读者将掌握许多这方面的知识。

在技术面试中脱颖而出

在过去的几年中，很多读者分享了“算法详解”系列图书如何帮助他们在技术面试中脱颖而出的经历。

其他算法教材

“算法详解”系列图书的目标是以读者容易接受的方式介绍算法的基础知识。尽管如此，市场上仍有很多非常优秀、更为传统和全面的算法教材，它们可以作为“算法详解”系列关于算法的其他细节、问题和主题的有益补充。我鼓励读者去探索和寻找自己喜欢的其他教材。此外，还有很多教材专注于特定编程语言的成熟算法实现，这些教材从程序员的角度讲解。在网络上也有大量免费提供这些算法实现代码的资源。

本书的目标读者

“算法详解”系列图书以及基于在线课程的整体目标是尽可能吸引更广泛的读者群体。学习本书在线课程的学生来自不同的年龄、背景和生活方式，其中包括高中生、大学生、现有和未来的软件工程师、科学家和专业人员，他们遍布世界各地。

本书不是一本编程教程，理想情况下，读者至少应该熟悉一种标准的编程语言（如Java、Python、C、Scala、Haskell等），并掌握基本的编程技巧。作为一个快速测试，读者可以尝试阅读第2.2节。如果读者觉得自己理解了，那么理解本书的其他部分应该也不会有问题。如果读者想提高自己的编程技术水平，可以学习一些免费提供基础编程教学的在线课程。

根据需要，我们将通过数学分析来帮助读者理解算法实现目标的原理和过程。Eric Lehman、F. Thomson Leighton和Albert R. Meyer关于计算机科学数学知识的免费课程是非常有价值的资源，可以帮助读者复习数学符号、数学证明的基本知识（如归纳法、悖论等）、离散概率等。