算法分析與設計技巧（簡體書）

全書共分5章，第1章介紹了演算法的概念與評價，第2章介紹了遞迴法、分治法、貪心法、搜索法和回溯法這些常用演算法的概念與基本思想及其應用，第3章對動態規劃演算法從其基本思想與概念、解題步驟與方法、簡單應用與優化等進行了全面深入的研究，第4章著重討論了搜索演算法及其優化技巧，第5章討論了圖上的演算法：並查集、生成樹、最短路、強連通分量、2-SAT、差分約束、二分圖以及網路流的演算法分析與設計技巧。

第1章 演算法的概念 1
1.1 演算法的概念和描述 1
1.1.1 演算法的概念 1
1.1.2 演算法的描述 3
1.2 演算法的時間複雜度和空間複雜度 4
1.2.1 演算法的評價 4
1.2.2 演算法的時間複雜度 5
1.2.3 演算法的空間複雜度 11
習題1 12
第2章 常用演算法 18
2.1 遞迴法 18
2.1.1 遞迴的概念與基本思想 18
2.1.2 遞迴法的應用 19
2.2 分治法 23
2.2.1 分治的概念與基本思想 23
2.2.2 分治法的應用 27
2.3 貪心法 34
2.3.1 貪心的概念與基本思想 34
2.3.2 貪心法的應用 34
2.4 搜索法與回溯法 42
2.4.1 搜索與回溯的概念與基本思想 42
2.4.2 搜索法與回溯法的應用 43
習題2 48
第3章 動態規劃 53
3.1 動態規劃的基本思想與概念 53
3.1.1 動態規劃的基本思想 53
3.1.2 動態規劃的概念 55
3.1.3 動態規劃的常用名詞 56
3.1.4 動態規劃演算法的基本步驟 56
3.2 動態規劃的簡單應用 58
3.2.1 線性動態規劃 58
3.2.2 背包動態規劃 69
3.2.3 區間動態規劃 79
3.2.4 網格動態規劃 82
3.3 動態規劃的深入研究 88
3.3.1 樹形動態規劃 88
3.3.2 狀態壓縮動態規劃 95
3.3.3 基於連通性的狀態壓縮動態規劃 104
3.3.4 數位元數目類動態規劃 112
3.4 動態規劃的優化方法 115
3.4.1 減少狀態總數 115
3.4.2 利用資料結構加速狀態轉移過程 120
3.4.3 四邊形不等式優化 124
3.4.4 斜率優化 126
習題3 129
第4章 搜索演算法中的優化技巧 138
4.1 搜索中的剪枝技巧 138
4.2 選擇合適的搜索方向 158
4.3 A*演算法 171
4.4 跳舞鏈 181
4.5 搜索還是動態規劃 194
習題4 205
第5章 圖上的演算法 209
5.1 並查集 209
5.2 生成樹 220
5.3 最短路 230
5.4 強連通分量 239
5.5 2SAT 250
5.6 差分約束 261
5.7 二分圖 266
5.8 網路流 279
5.8.1 網路流的概念 279
5.8.2 最大流的求解方法 280
習題5 299
參考文獻 306