第1章 算法与数学 1
1.1 复杂性的计量 2
1.2 生成函数 5
1.3 递归方程求解 8
1.4 和与积 17
1.5 组合公式 20
1.6 思考题 22
第2章 分治算法 24
2.1 大整数的乘法 25
2.2 棋盘覆盖问题 29
2.3 循环赛日程表 32
2.4 矩阵乘法 37
2.5 思考题 43
第3章 动态规划法 45
3.1 DNA比对 50
3.2 最长公共子序列 52
3.3 计算矩阵连乘积 55
3.4 思考题 60
第4章 贪心算法 62
4.1 01背包 64
4.2 拓扑排序 67
4.3 最小生成树 72
4.4 汽车加油问题 79
4.5 思考题 81
第5章 回溯法 84
5.1 4皇后问题 85
5.2 排列组合问题 89
5.3 01背包问题 91
5.4 任务分配问题 95
5.5 桥本分数式 97
5.6 思考题 100
第6章 分支限界法 104
6.1 01背包 105
6.2 装载问题 111
6.3 布线问题 116
6.4 思考题 124
第7章 数论及Fibonacci数列 127
7.1 欧几里德定律 127
7.2 中国剩余定理 132
7.3 Fibonacci数列 135
7.4 Fibonacci与矩阵连乘 141
7.5 思考题 143
第8章 图 145
8.1 图的遍历 145
8.2 最短路径问题 151
8.3 最大流 160
8.4 二部图最大匹配 169
8.5 思考题 173
第9章 组合问题与大数运算 176
9.1 大数运算 176
9.2 平面幻方 181
9.3 Catalan数 186
9.4 Pólya计数法 189
9.5 思考题 195
第10章 背包问题 196
10.1 01背包问题 196
10.2 完备背包 200
10.3 多重背包 203
10.4 混合背包 205
10.5 二维背包的费用问题 207
10.6 分组的背包问题 209
10.7 有依赖的背包问题 211
10.8 泛化问题 214
10.9 思考题 216
第11章 博弈 217
11.1 巴什博奕 218
11.2 威佐夫博奕 221
11.3 Ferguson博弈 223
11.4 斐波那契博弈 225
11.5 尼姆博奕 227
11.6 SG函数与SG定理 228
11.7 思考题 233
参考文献 235