算法之禅：递推与递归

聚二十年功力，呈禅意才思、匠心代码

探因由，究所以

递推递归双重实现，打通算法任督二脉

文品其思，码鉴其才

亲爱的读者，当你读到这篇致谢的时候，你应该还没有开始正文的阅读，因为大多数时候“致谢”都紧跟在一本书的序言之后。而对于我们作者来说，“致谢”则常常是需要为一本书撰写的最后部分，因为这时候整本书的编辑、勘校、排版等工作已经收尾，马上就要印刷发行了。对于我而言，“致谢”也是最激动人心的部分，因为在这里出现的都是与本书出版相关的、最重要的人们—它就像一个时空隧道，几十年后打开它，依然会让我想起这些朋友、让一件件往事历历在目。

本书的顺利出版，首先要感谢中国水利水电出版社的周春元先生。若不是周先生慷慨接纳我的文字并组织最优秀的团队将之编辑成册，恐怕这些有趣的内容会永远躺在互联网的某个角落里、无缘与大家相见。次者，我要将我最诚挚的谢意献给本书的责任编辑陈洁女士，是她亲自用一双慧眼和化腐朽为神奇的能力将我那堆粗鄙不堪的文字编辑成一本让人赏心悦目、爱不释手的书籍。你可能会想：“不就是作者对出版社的日常吹捧嘛，有什么！”还真不是这样。试想，如果你看到一个讲算法的作者把Java虚拟机的缩写写成JMV（正确的应该是JVM），你会怎么想？你一定会想：“你到底会不会编程啊？还讲算法！”是的，就像你所感受到的，内容当中的“低级错误”伤害的已经不仅仅是阅读体验，伤害更多的恐怕是读者对内容和对我的信任。而前面这个错误，正是我亲手写下的、几十上百个错误中的一个（而且不是最“丢人”的一个）。对于程序员而言，“笔误”这个东西是不存在的，因为无论是脑子抽筋还是笔误，所产生的错误代码都会让程序崩溃。整个编辑和勘校过程，自始至终，陈编辑都与我保持着十分密切的联系。每次她发来的编辑建议中，都会有那么几个让我汗颜自责的错误，甚至怀疑自己培养了十多年的职业素养是不是都拿来喂邻居家的哈士奇了。万幸有陈编辑鼎力相助，才让这本书在这么快的时间顺利出版。陈编辑不但治学严谨，而且十分耐心—编辑过程中，经常是她刚刚编辑好一章，我就对原稿内容做了补充或者修改，而陈编辑从来没有怨言、马上就做出相应的调整，让我十分感动。让我们一起为她点赞！另外，尽管本书中的代码在我本机上都能顺利运行，但这并不意味着其中就100%没有bug，而且，代码中的bug也完全超出了编辑团队的知识范围。所以，如果大家发现错误—算我的，请不要责怪编辑团队。我一定会以最快的速度改正错误。

我小的时候，家里经济条件不好，按理说是没有机会接触到计算机并最终以计算机科学作为自己职业生涯的。所以，我一生都要感谢我的计算机启蒙老师—刘晓林先生。正是他用自家的286将我带上了计算机科学的道路，让我认识到了什么是DOS，什么是Windows，什么是编程。一转眼我已经成长到了当年刘叔叔教我计算机的年龄—我也将肩负起一个先行者的责任，将计算机科学技术普及给更多的新人，让更多的新生代年轻人接触到这个行业。

跟师父进门后，我之所以能够继续在计算机科学领域扎根、发展，全靠志同道合的伙伴们引领和鼓励。在这些伙伴中，对我影响比较深远的有这么几位：刘扬（初中挚友，刘叔叔的儿子）、张博（高中挚友，现在在上海从事法律与计算机科学结合的创新、创业）、谢志威（大学挚友，现在是小学校长）、余峰（旅美后的职业发展榜样，现就职于Google）。感谢生命中有你们的出现。

计算机科学行业是丰富多彩的。进入行业后，我遇到了形形色色的人们，也有了些许起起伏伏的经历。感谢每一位曾经与我有过交集的朋友，感谢每一分信任、每一次鼓励、每一个挑战……在你们身上，我发现了无穷无尽的优点，也从你们那里学到了很多之前不曾具备的能力。是你们，让我从一个鲁莽无知的少年，成为了一个稳健前行的中年人。是你们，让我认识到“尊重真理，尊重人性”是一种多么珍贵的品质。

致谢
一夜春风，万树梨花

第00章 开篇绪言
缘起 1
预备知识 3
第01章 思想与实现
思想 6
实现 8
准备一棵树 9
用递推代码实现递推思想 11
用递归代码实现递推思想 13
用递归代码实现递归思想 15
“好”的递归与“坏”的递归 16
用递推代码实现递归思想 20
思考题 23
第02章 回溯：上古神话中的算法
回溯式递归的基本原理 24
示例1 25
示例2 26
神话故事中的算法 27
迷宫设计入门 28
探寻迷宫中的路径 29
用递推（循环）代码实现回溯 32
思考题 33
第03章 动态规划：动机决定性质
什么是动态规划 35
透彻理解动态规划 36
递推版动态规划 37
递归版动态规划 39
陷阱：这不是动态规划！ 42
贪心也要动脑子 43
更上层楼：让规划“动态”起来 46
切年糕 46
接订单 48
听讲座 56
思考题 60
动态规划哲思 60
第04章 排序：算法皇冠上的明珠
游乐园：O(n^2)的简单排序们 63
选择排序 63
冒泡排序 64
插入排序 66
以空间换时间：归并排序 66
看运气的快速排序 68
两全其美：堆排序 71
什么是“堆” 71
构建大/小根堆 72
利用“大根堆”进行原地排序 75
利用“小根堆”生成升序数组 75
思考题 76
第05章 查找：来而不往非礼也
二分查找 78
在已排序的数组上 79
在平衡二叉搜索树上 80
线段树：化繁为简 81
构建线段树 82
查询子段和 84
字典树：字母大接龙 86
递推版实现 87
递归版实现 89
并查集：朋友的朋友是朋友 90
第06章 图：包罗万象
图的表达 94
邻接列表 95
邻接矩阵 97
应对向、权、环的变化 98
思考题 100
图的遍历 100
广度优先遍历 101
深度优先遍历 103
递推版深度优先遍历 105
向、权、环对遍历的影响 106
顶点的连通性 107
有无权重对连通性的影响 109
有无向对连通性的影响 110
环对连通性的影响 113
强连通性组件 113
Kosaraju-Sharir算法 114
图上的路径 116
BFS式路径搜寻 118
DFS式路径搜寻 119
自底向上式路径搜寻 119
回溯式路径搜寻 121
获取环路 122
思考题 123
最短路径 124
Dijkstra最短路径算法 125
Bellman-Ford最短路径算法 129
Floyd-Warshall最短路径算法 131
最小生成树 133
构建有权无向图 134
Prim算法 136
Kruskal算法 137
最大流：超时空移花接木 138
余量边，反向边，余量网络，增益路径 139
容量返还 140
Ford-Fulkerson算法实现 143
最小割：流量的瓶颈 145
拓扑排序 147
生成入度图与出度图 148
理解顶点的入度 149
递推实现 150
递归实现 151
思考题 152
后记