算法之禪：遞推與遞歸

致謝
一夜春風，萬樹梨花
第00章  開篇緒言
緣起 1
預備知識 3
第01章  思想與實現(xiàn)
思想 6
實現(xiàn) 8
準備一棵樹 9
用遞推代碼實現(xiàn)遞推思想 11
用遞歸代碼實現(xiàn)遞推思想 13
用遞歸代碼實現(xiàn)遞歸思想 15
“好”的遞歸與“壞”的遞歸 16
用遞推代碼實現(xiàn)遞歸思想 20
思考題 23
第02章  回溯：上古神話中的算法
回溯式遞歸的基本原理 24
示例1 25
示例2 26
神話故事中的算法 27
迷宮設計入門 28
探尋迷宮中的路徑 29
用遞推（循環(huán)）代碼實現(xiàn)回溯 32
思考題 33
第03章  動態(tài)規(guī)劃：動機決定性質
什么是動態(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
構建大/小根堆 72
利用“大根堆”進行原地排序 75
利用“小根堆”生成升序數(shù)組 75
思考題 76
第05章  查找：來而不往非禮也
二分查找 78
在已排序的數(shù)組上 79
在平衡二叉搜索樹上 80
線段樹：化繁為簡 81
構建線段樹 82
查詢子段和 84
字典樹：字母大接龍 86
遞推版實現(xiàn) 87
遞歸版實現(xiàn) 89
并查集：朋友的朋友是朋友 90
第06章  圖：包羅萬象
圖的表達 94
鄰接列表 95
鄰接矩陣 97
應對向、權、環(huán)的變化 98
思考題 100
圖的遍歷 100
廣度優(yōu)先遍歷 101
深度優(yōu)先遍歷 103
遞推版深度優(yōu)先遍歷 105
向、權、環(huán)對遍歷的影響 106
頂點的連通性 107
有無權重對連通性的影響 109
有無向對連通性的影響 110
環(huán)對連通性的影響 113
強連通性組件 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
構建有權無向圖 134
Prim算法 136
Kruskal算法 137
流：超時空移花接木 138
余量邊，反向邊，余量網(wǎng)絡，增益路徑 139
容量返還 140
Ford-Fulkerson算法實現(xiàn) 143
小割：流量的瓶頸 145
拓撲排序 147
生成入度圖與出度圖 148
理解頂點的入度 149
遞推實現(xiàn) 150
遞歸實現(xiàn) 151
思考題 152
后記