算法之禪：遞推與遞歸

致謝
一夜春風(fēng)，萬樹梨花
第00章  開篇緒言
緣起 1
預(yù)備知識(shí) 3
第01章  思想與實(shí)現(xiàn)
思想 6
實(shí)現(xiàn) 8
準(zhǔn)備一棵樹 9
用遞推代碼實(shí)現(xiàn)遞推思想 11
用遞歸代碼實(shí)現(xiàn)遞推思想 13
用遞歸代碼實(shí)現(xiàn)遞歸思想 15
“好”的遞歸與“壞”的遞歸 16
用遞推代碼實(shí)現(xiàn)遞歸思想 20
思考題 23
第02章  回溯：上古神話中的算法
回溯式遞歸的基本原理 24
示例1 25
示例2 26
神話故事中的算法 27
迷宮設(shè)計(jì)入門 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)”起來 46
切年糕 46
接訂單 48
聽講座 56
思考題 60
動(dòng)態(tài)規(guī)劃哲思 60
第04章  排序：算法皇冠上的明珠
游樂園：O(n^2)的簡單排序們 63
選擇排序 63
冒泡排序 64
插入排序 66
以空間換時(shí)間：歸并排序 66
看運(yùn)氣的快速排序 68
兩全其美：堆排序 71
什么是“堆” 71
構(gòu)建大/小根堆 72
利用“大根堆”進(jìn)行原地排序 75
利用“小根堆”生成升序數(shù)組 75
思考題 76
第05章  查找：來而不往非禮也
二分查找 78
在已排序的數(shù)組上 79
在平衡二叉搜索樹上 80
線段樹：化繁為簡 81
構(gòu)建線段樹 82
查詢子段和 84
字典樹：字母大接龍 86
遞推版實(shí)現(xiàn) 87
遞歸版實(shí)現(xiàn) 89
并查集：朋友的朋友是朋友 90
第06章  圖：包羅萬象
圖的表達(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
有無權(quán)重對(duì)連通性的影響 109
有無向?qū)B通性的影響 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
小生成樹 133
構(gòu)建有權(quán)無向圖 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
后記