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

探因由，究所以

遞推遞歸雙重實現(xiàn)，打通算法任督二脈

文品其思，碼鑒其才

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

本書的順利出版，首先要感謝中國水利水電出版社的周春元先生。若不是周先生慷慨接納我的文字并組織最優(yōu)秀的團(tuán)隊將之編輯成冊，恐怕這些有趣的內(nèi)容會永遠(yuǎn)躺在互聯(lián)網(wǎng)的某個角落里、無緣與大家相見。次者，我要將我最誠摯的謝意獻(xiàn)給本書的責(zé)任編輯陳潔女士，是她親自用一雙慧眼和化腐朽為神奇的能力將我那堆粗鄙不堪的文字編輯成一本讓人賞心悅目、愛不釋手的書籍。你可能會想：“不就是作者對出版社的日常吹捧嘛，有什么！”還真不是這樣。試想，如果你看到一個講算法的作者把Java虛擬機(jī)的縮寫寫成JMV（正確的應(yīng)該是JVM），你會怎么想？你一定會想：“你到底會不會編程啊？還講算法！”是的，就像你所感受到的，內(nèi)容當(dāng)中的“低級錯誤”傷害的已經(jīng)不僅僅是閱讀體驗，傷害更多的恐怕是讀者對內(nèi)容和對我的信任。而前面這個錯誤，正是我親手寫下的、幾十上百個錯誤中的一個（而且不是最“丟人”的一個）。對于程序員而言，“筆誤”這個東西是不存在的，因為無論是腦子抽筋還是筆誤，所產(chǎn)生的錯誤代碼都會讓程序崩潰。整個編輯和勘校過程，自始至終，陳編輯都與我保持著十分密切的聯(lián)系。每次她發(fā)來的編輯建議中，都會有那么幾個讓我汗顏自責(zé)的錯誤，甚至懷疑自己培養(yǎng)了十多年的職業(yè)素養(yǎng)是不是都拿來喂鄰居家的哈士奇了。萬幸有陳編輯鼎力相助，才讓這本書在這么快的時間順利出版。陳編輯不但治學(xué)嚴(yán)謹(jǐn)，而且十分耐心—編輯過程中，經(jīng)常是她剛剛編輯好一章，我就對原稿內(nèi)容做了補(bǔ)充或者修改，而陳編輯從來沒有怨言、馬上就做出相應(yīng)的調(diào)整，讓我十分感動。讓我們一起為她點贊！另外，盡管本書中的代碼在我本機(jī)上都能順利運行，但這并不意味著其中就100%沒有bug，而且，代碼中的bug也完全超出了編輯團(tuán)隊的知識范圍。所以，如果大家發(fā)現(xiàn)錯誤—算我的，請不要責(zé)怪編輯團(tuán)隊。我一定會以最快的速度改正錯誤。

我小的時候，家里經(jīng)濟(jì)條件不好，按理說是沒有機(jī)會接觸到計算機(jī)并最終以計算機(jī)科學(xué)作為自己職業(yè)生涯的。所以，我一生都要感謝我的計算機(jī)啟蒙老師—劉曉林先生。正是他用自家的286將我?guī)�上了計算機(jī)科學(xué)的道路，讓我認(rèn)識到了什么是DOS，什么是Windows，什么是編程。一轉(zhuǎn)眼我已經(jīng)成長到了當(dāng)年劉叔叔教我計算機(jī)的年齡—我也將肩負(fù)起一個先行者的責(zé)任，將計算機(jī)科學(xué)技術(shù)普及給更多的新人，讓更多的新生代年輕人接觸到這個行業(yè)。

跟師父進(jìn)門后，我之所以能夠繼續(xù)在計算機(jī)科學(xué)領(lǐng)域扎根、發(fā)展，全靠志同道合的伙伴們引領(lǐng)和鼓勵。在這些伙伴中，對我影響比較深遠(yuǎn)的有這么幾位：劉揚（初中摯友，劉叔叔的兒子）、張博（高中摯友，現(xiàn)在在上海從事法律與計算機(jī)科學(xué)結(jié)合的創(chuàng)新、創(chuàng)業(yè)）、謝志威（大學(xué)摯友，現(xiàn)在是小學(xué)校長）、余峰（旅美后的職業(yè)發(fā)展榜樣，現(xiàn)就職于Google）。感謝生命中有你們的出現(xiàn)。

計算機(jī)科學(xué)行業(yè)是豐富多彩的。進(jìn)入行業(yè)后，我遇到了形形色色的人們，也有了些許起起伏伏的經(jīng)歷。感謝每一位曾經(jīng)與我有過交集的朋友，感謝每一分信任、每一次鼓勵、每一個挑戰(zhàn)……在你們身上，我發(fā)現(xiàn)了無窮無盡的優(yōu)點，也從你們那里學(xué)到了很多之前不曾具備的能力。是你們，讓我從一個魯莽無知的少年，成為了一個穩(wěn)健前行的中年人。是你們，讓我認(rèn)識到“尊重真理，尊重人性”是一種多么珍貴的品質(zhì)。

致謝
一夜春風(fēng)，萬樹梨花

第00章 開篇緒言
緣起 1
預(yù)備知識 3
第01章 思想與實現(xiàn)
思想 6
實現(xiàn) 8
準(zhǔn)備一棵樹 9
用遞推代碼實現(xiàn)遞推思想 11
用遞歸代碼實現(xiàn)遞推思想 13
用遞歸代碼實現(xiàn)遞歸思想 15
“好”的遞歸與“壞”的遞歸 16
用遞推代碼實現(xiàn)遞歸思想 20
思考題 23
第02章 回溯：上古神話中的算法
回溯式遞歸的基本原理 24
示例1 25
示例2 26
神話故事中的算法 27
迷宮設(shè)計入門 28
探尋迷宮中的路徑 29
用遞推（循環(huán)）代碼實現(xiàn)回溯 32
思考題 33
第03章 動態(tài)規(guī)劃：動機(jī)決定性質(zhì)
什么是動態(tài)規(guī)劃 35
透徹理解動態(tài)規(guī)劃 36
遞推版動態(tài)規(guī)劃 37
遞歸版動態(tài)規(guī)劃 39
陷阱：這不是動態(tài)規(guī)劃！ 42
貪心也要動腦子 43
更上層樓：讓規(guī)劃“動態(tài)”起來 46
切年糕 46
接訂單 48
聽講座 56
思考題 60
動態(tài)規(guī)劃哲思 60
第04章 排序：算法皇冠上的明珠
游樂園：O(n^2)的簡單排序們 63
選擇排序 63
冒泡排序 64
插入排序 66
以空間換時間：歸并排序 66
看運氣的快速排序 68
兩全其美：堆排序 71
什么是“堆” 71
構(gòu)建大/小根堆 72
利用“大根堆”進(jìn)行原地排序 75
利用“小根堆”生成升序數(shù)組 75
思考題 76
第05章 查找：來而不往非禮也
二分查找 78
在已排序的數(shù)組上 79
在平衡二叉搜索樹上 80
線段樹：化繁為簡 81
構(gòu)建線段樹 82
查詢子段和 84
字典樹：字母大接龍 86
遞推版實現(xiàn) 87
遞歸版實現(xiàn) 89
并查集：朋友的朋友是朋友 90
第06章 圖：包羅萬象
圖的表達(dá) 94
鄰接列表 95
鄰接矩陣 97
應(yīng)對向、權(quán)、環(huán)的變化 98
思考題 100
圖的遍歷 100
廣度優(yōu)先遍歷 101
深度優(yōu)先遍歷 103
遞推版深度優(yōu)先遍歷 105
向、權(quán)、環(huán)對遍歷的影響 106
頂點的連通性 107
有無權(quán)重對連通性的影響 109
有無向?qū)�連通性的影響 110
環(huán)對連通性的影響 113
強(qiáng)連通性組件 113
Kosaraju-Sharir算法 114
圖上的路徑 116
BFS式路徑搜尋 118
DFS式路徑搜尋 119
自底向上式路徑搜尋 119
回溯式路徑搜尋 121
獲取環(huán)路 122
思考題 123
最短路徑 124
Dijkstra最短路徑算法 125
Bellman-Ford最短路徑算法 129
Floyd-Warshall最短路徑算法 131
最小生成樹 133
構(gòu)建有權(quán)無向圖 134
Prim算法 136
Kruskal算法 137
最大流：超時空移花接木 138
余量邊，反向邊，余量網(wǎng)絡(luò)，增益路徑 139
容量返還 140
Ford-Fulkerson算法實現(xiàn) 143
最小割：流量的瓶頸 145
拓?fù)渑判?147
生成入度圖與出度圖 148
理解頂點的入度 149
遞推實現(xiàn) 150
遞歸實現(xiàn) 151
思考題 152
后記