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

探因由，究所以

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

文品其思，碼鑒其才

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

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

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

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

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

致謝
一夜春風(fēng)，萬(wàn)樹(shù)梨花

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