趣學(xué)算法（第2版）

第 1章　算法之美 1
1.1　打開算法之門 2
1.2　妙不可言—算法復(fù)雜性 2
1.3　一棋盤的麥子 8
1.4　神奇的兔子數(shù)列 9
1.5　算法學(xué)習(xí)瓶頸 14
1.6　本章小結(jié) 15
第 2章　貪心算法 16
2.1　貪心算法基礎(chǔ) 17
2.1.1 貪心本質(zhì) 17
2.1.2 貪亦有道 17
2.1.3 貪心算法秘籍 18
2.2　最優(yōu)裝載問題 18
2.2.1 問題分析 18
2.2.2 算法設(shè)計(jì) 18
2.2.3 完美圖解 19
2.2.4 算法詳解 19
2.2.5 算法分析及優(yōu)化拓展 20
2.3　阿里巴巴與四十大盜—背包問題 21
2.3.1 問題分析 21
2.3.2 算法設(shè)計(jì) 22
2.3.3 完美圖解 22
2.3.4 算法詳解 23
2.3.5 算法分析及優(yōu)化拓展 24
2.4　高級(jí)鐘點(diǎn)秘書—會(huì)議安排 24
2.4.1 問題分析 25
2.4.2 算法設(shè)計(jì) 26
2.4.3 完美圖解 26
2.4.4 算法詳解 27
2.4.5 算法分析及優(yōu)化拓展 28
2.5　一場說走就走的旅行—最短路徑 28
2.5.1 問題分析 29
2.5.2 算法設(shè)計(jì) 29
2.5.3 完美圖解 30
2.5.4 算法詳解 33
2.5.5 算法分析及優(yōu)化拓展 34
2.6　神秘電報(bào)密碼—霍夫曼編碼 36
2.6.1 問題分析 37
2.6.2 算法設(shè)計(jì) 38
2.6.3 完美圖解 38
2.6.4 算法詳解 41
2.6.5 算法分析及優(yōu)化拓展 48
2.7　溝通無限校園網(wǎng)—最小生成樹 49
2.7.1 問題分析 49
2.7.2 Prim算法 50
2.7.3 完美圖解 51
2.7.4 算法詳解 56
2.7.5 算法分析及優(yōu)化拓展 57
2.7.6 Kruskal算法 57
第3章　分治算法 62
3.1　分治算法基礎(chǔ) 63
3.1.1 分而治之 63
3.1.2 分治算法要素 63
3.1.3 分治算法秘籍 63
3.2　二分搜索 64
3.2.1 問題分析 64
3.2.2 算法設(shè)計(jì) 64
3.2.3 完美圖解 65
3.2.4 算法詳解 66
3.2.5 算法分析及優(yōu)化拓展 66
3.3　合并排序 68
3.3.1 問題分析 68
3.3.2 算法設(shè)計(jì) 68
3.3.3 完美圖解 68
3.3.4 算法詳解 68
3.3.5 算法分析及優(yōu)化拓展 71
3.4　快速排序 72
3.4.1 問題分析 72
3.4.2 算法設(shè)計(jì) 73
3.4.3 完美圖解 74
3.4.4 算法詳解 75
3.4.5 算法分析及優(yōu)化拓展 76
3.5　分治算法復(fù)雜度求解秘籍 79
3.5.1 遞推法 79
3.5.2 遞歸樹 80
3.5.3 大師解法 80
第4章　動(dòng)態(tài)規(guī)劃算法 84
4.1　動(dòng)態(tài)規(guī)劃算法基礎(chǔ) 85
4.1.1　算法思想 85
4.1.2　算法要素 85
4.1.3　解題秘訣 86
4.2　爬樓梯 86
4.2.1　問題分析 86
4.2.2　算法詳解 87
4.2.3　算法分析及優(yōu)化拓展 88
4.3　最長上升子序列 89
4.3.1　問題分析 89
4.3.2　算法設(shè)計(jì) 89
4.3.3　完美圖解 90
4.3.4　算法詳解 91
4.3.5　算法分析及優(yōu)化拓展 91
4.4　最長公共子序列 93
4.4.1　問題分析 93
4.4.2　算法設(shè)計(jì) 95
4.4.3　完美圖解 96
4.4.4　算法詳解 99
4.4.5　算法分析及優(yōu)化拓展 100
4.5　編輯距離 100
4.5.1　問題分析 101
4.5.2　算法設(shè)計(jì) 102
4.5.3　完美圖解 102
4.5.4　算法詳解 105
4.5.5　算法分析及優(yōu)化拓展 106
4.6　游艇租賃 106
4.6.1　問題分析 106
4.6.2　算法設(shè)計(jì) 107
4.6.3　完美圖解 108
4.6.4　算法詳解 111
4.6.5　算法分析及優(yōu)化拓展 111
4.7　矩陣連乘 112
4.7.1　問題分析 112
4.7.2　算法設(shè)計(jì) 114
4.7.3　完美圖解 115
4.7.4　算法詳解 118
4.7.5　算法分析及優(yōu)化拓展 119
4.8　0/1背包問題 119
4.8.1　問題分析 120
4.8.2　算法設(shè)計(jì) 121
4.8.3　完美圖解 121
4.8.4　算法詳解 125
4.8.5　算法分析及優(yōu)化拓展 125
4.9　沒有上司的舞會(huì) 128
4.9.1　問題分析 128
4.9.2　算法設(shè)計(jì) 129
4.9.3　完美圖解 129
4.9.4　算法詳解 131
4.9.5　算法分析及優(yōu)化拓展 132
4.10　動(dòng)態(tài)規(guī)劃算法秘籍 132
第5章　回溯法 134
5.1　深度優(yōu)先搜索 135
5.1.1　算法思想 135
5.1.2　完美圖解 135
5.2　回溯法基礎(chǔ) 136
5.2.1　算法思想 136
5.2.2　算法要素 136
5.3　0/1背包問題 138
5.3.1　問題分析 138
5.3.2　算法設(shè)計(jì) 138
5.3.3　完美圖解 140
5.3.4　算法詳解 142
5.3.5　算法分析及優(yōu)化拓展 143
5.4　最大團(tuán) 144
5.4.1　問題分析 145
5.4.2　算法設(shè)計(jì) 145
5.4.3　完美圖解 147
5.4.4　算法詳解 151
5.4.5　算法分析及優(yōu)化拓展 152
5.5　地圖著色 153
5.5.1　問題分析 153
5.5.2　算法設(shè)計(jì) 153
5.5.3　完美圖解 155
5.5.4　算法詳解 158
5.5.5　算法分析及優(yōu)化拓展 159
5.6　n皇后問題 159
5.6.1　問題分析 160
5.6.2　算法設(shè)計(jì) 160
5.6.3　完美圖解 161
5.6.4　算法詳解 168
5.6.5　算法分析及優(yōu)化拓展 168
5.7　最優(yōu)加工順序 170
5.7.1　問題分析 170
5.7.2　算法設(shè)計(jì) 171
5.7.3　完美圖解 172
5.7.4　算法詳解 176
5.7.5　算法分析及優(yōu)化拓展 177
5.8　回溯法秘籍 177
第6章　分支限界法 179
6.1　廣度優(yōu)先搜索 180
6.1.1　算法思想 180
6.1.2　完美圖解 180
6.2　分支限界法基礎(chǔ) 182
6.2.1　算法思想 183
6.2.2　算法步驟 183
6.3　0/1背包問題 183
6.3.1　問題分析 184
6.3.2　算法設(shè)計(jì) 184
6.3.3　完美圖解 185
6.3.4　算法詳解 189
6.3.5　算法分析及優(yōu)化拓展 190
6.4　旅行商問題 194
6.4.1　問題分析 194
6.4.2　算法設(shè)計(jì) 194
6.4.3　完美圖解 195
6.4.4　算法詳解 198
6.4.5　算法分析及優(yōu)化拓展 199
6.5　最優(yōu)工程布線 200
6.5.1　問題分析 200
6.5.2　算法設(shè)計(jì) 201
6.5.3　完美圖解 201
6.5.4　算法詳解 207
6.5.5　算法分析及優(yōu)化拓展 208
6.6　回溯法與分支限界法的異同 209
第7章　網(wǎng)絡(luò)流算法 210
7.1　好的規(guī)劃帶來好效益—最大流 211
7.1.1 增廣路算法 212
7.1.2 完美圖解 213
7.2　最短增廣路—EK算法 215
7.2.1 算法設(shè)計(jì) 215
7.2.2 完美圖解 216
7.2.3 算法詳解 221
7.2.4 算法分析 223
7.3　峰回路轉(zhuǎn)—Dinic算法 223
7.3.1 算法設(shè)計(jì) 223
7.3.2 完美圖解 223
7.3.3 算法詳解 225
7.3.4 算法分析 226
7.3.5 當(dāng)前弧優(yōu)化 226
7.4　一蹴而就—ISAP算法 227
7.4.1 算法設(shè)計(jì) 228
7.4.2 完美圖解 229
7.4.3 算法詳解 231
7.4.4 算法分析 232
7.5　最小費(fèi)用最大流—最小費(fèi)用路算法 232
7.5.1 算法設(shè)計(jì) 233
7.5.2 完美圖解 233
7.5.3 算法詳解 234
7.5.4 算法分析 235
7.5.5 消圈算法 235
7.6　最大匹配問題 237
7.6.1 問題分析 237
7.6.2 算法設(shè)計(jì) 238
7.6.3 完美圖解 238
7.6.4 算法詳解 239
7.6.5 算法分析 239
7.6.6 匈牙利算法 239
7.7　試題庫問題 242
7.7.1 問題分析 242
7.7.2 算法設(shè)計(jì) 242
7.7.3 完美圖解 243
7.7.4 算法詳解 244
7.7.5 算法分析 245
7.8　最大收益問題 245
7.8.1 問題分析 245
7.8.2 算法設(shè)計(jì) 246
7.8.3 完美圖解 247
7.8.4 算法詳解 249
7.8.5 算法分析 249
7.9　旅游路線問題 249
7.9.1 問題分析 250
7.9.2 算法設(shè)計(jì) 251
7.9.3 完美圖解 251
7.9.4 算法詳解 252
7.9.5 算法分析 254
7.10　網(wǎng)絡(luò)流問題求解秘籍 254
第8章　實(shí)用算法 255
8.1　啟發(fā)式搜索在游戲中的應(yīng)用 256
8.1.1 A*算法 256
8.1.2 IDA*算法 256
8.1.3 八數(shù)碼游戲 257
8.2　多模匹配算法在敏感詞過濾中的應(yīng)用 264
8.2.1 字典樹 265
8.2.2 AC自動(dòng)機(jī) 269
8.2.3 敏感詞過濾 272
8.3　LRU緩存淘汰算法的應(yīng)用場景 273
8.3.1 LRU算法 274
8.3.2 哈希鏈表 275
8.3.3 算法詳解 277
8.3.4 算法分析 280
8.4　高頻面試算法 280
8.4.1 快慢指針 280
8.4.2 棧的最小值 288
8.4.3 滑動(dòng)窗口中的最大值 289
8.4.4 零錢兌換 293
8.4.5 股票買賣秘籍 295
附錄A　特征方程和通項(xiàng)公式 299
附錄B　sort函數(shù) 302
附錄C　優(yōu)先隊(duì)列 305
附錄D　鄰接表 312
附錄E　并查集 318
附錄F　四邊不等式 323
附錄G　排列樹 327
附錄H　貝爾曼規(guī)則 339
附錄I　增廣路中每條邊成為關(guān)鍵邊的次數(shù) 342