聚二十年功力，呈禪意才思、匠心代碼

探因由，究所以

遞推遞歸雙重實現，打通算法任督二脈

文品其思，碼鑒其才

親愛的讀者，當你讀到這篇致謝的時候，你應該還沒有開始正文的閱讀，因為大多數時候“致謝”都緊跟在一本書的序言之后。而對于我們作者來說，“致謝”則常常是需要為一本書撰寫的最后部分，因為這時候整本書的編輯、勘校、排版等工作已經收尾，馬上就要印刷發行了。對于我而言，“致謝”也是最激動人心的部分，因為在這里出現的都是與本書出版相關的、最重要的人們—它就像一個時空隧道，幾十年后打開它，依然會讓我想起這些朋友、讓一件件往事歷歷在目。

本書的順利出版，首先要感謝中國水利水電出版社的周春元先生。若不是周先生慷慨接納我的文字并組織最優秀的團隊將之編輯成冊，恐怕這些有趣的內容會永遠躺在互聯網的某個角落里、無緣與大家相見。次者，我要將我最誠摯的謝意獻給本書的責任編輯陳潔女士，是她親自用一雙慧眼和化腐朽為神奇的能力將我那堆粗鄙不堪的文字編輯成一本讓人賞心悅目、愛不釋手的書籍。你可能會想：“不就是作者對出版社的日常吹捧嘛，有什么！”還真不是這樣。試想，如果你看到一個講算法的作者把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
后記