目录
CONTENTS
第 1章 最长不下降子序列问题
1.1.最长不下降子序列 / 1
1.2.抄近路 / 6
1.3.宝藏 / 7
1.4.导弹拦截 / 8
1.5.和谐俱乐部 / 9
1.6.滑雪 / 10
1.7.拓展与练习 / 12
第 2章 背包问题
2.1.简单背包问题 / 13
2.2.0/1背包问题 / 15
2.3.0/1背包算法的优化 / 17
2.4.分组背包问题 / 18
2.4.1.二维数组动态规划算法 / 19
2.4.2.一维数组优化算法 / 20
2.5.拓展与练习 / 21
第3章 完全背包问题
3.1.完全背包 / 22
3.2.完全背包算法的优化 / 23
3.3.拓展与练习 / 24
第4章 多重背包问题
4.1.多重背包 / 25
4.2.通天塔 / 27
4.3.忙碌 / 28
4.4.拓展与练习 / 29
第5章 二维费用背包问题
5.1.训练赛 / 30
5.2.电脑游戏 / 31
5.3.拓展与练习 / 32
第6章 区间动态规划
6.1.书架问题1 / 33
6.2.书架问题2 / 35
6.3.收购珍珠 / 37
6.4.双色马 / 38
6.5.归并石子１ / 39
6.6.切割铜棒 / 44
6.7.邮局问题 / 45
6.8.乘积最大 / 47
6.9.凸多边形三角划分 / 49
6.10.凸多边形分割 / 51
6.11.拓展与练习 / 54
第7章 路径问题
7.1.最短路径 / 55
7.2.最少交通费用问题 / 60
7.3.拓展与练习 / 62
第8章 资源类动态规划
8.1.机器分配 / 63
8.2.调度问题 / 64
8.3.系统可靠性 / 66
8.4.购物 / 67
8.5.快餐问题 / 69
8.6.拓展与练习 / 71
第9章 动态规划的简单优化
9.1.丝绸之路 / 72
9.1.1.动态规划算法一 / 73
9.1.2.动态规划算法二 / 73
9.1.3.动态规划算法三 / 74
9.2.双人游戏 / 75
9.2.1.动态规划算法一 / 76
9.2.2.动态规划算法二 / 76
9.3.理想收入问题 / 77
9.3.1.朴素算法 / 78
9.3.2.优化算法一 / 78
9.3.3.优化算法二 / 79
9.3.4.优化算法三 / 80
9.3.5.优化算法四 / 80
9.3.6.贪心算法 / 81
9.4.唱片录制 / 82
9.4.1.动态规划算法一 / 83
9.4.2.动态规划算法二 / 84
9.4.3.动态规划算法三 / 85
9.5.相遇问题 / 86
9.5.1.动态规划算法 / 87
9.5.2.普通递归算法 / 89
9.5.3.优化递归算法 / 91
9.5.4.宽度优先搜索算法 / 92
9.5.5.动态规划算法的优化 / 93
9.6.拓展与练习 / 96
第 10章 最大连续子序列问题
10.1.最大连续子序列和 / 97
10.2.最大连续子序列积 / 98
10.3.k个最大连续子序列和 / 99
10.4.拓展与练习 / 101
第 11章 子矩阵问题
11.1.二维最大子矩阵问题 / 102
11.2.扩展最大子矩阵问题 / 104
11.3.子矩阵变形问题 / 105
11.4.拓展与练习 / 107
第 12章 子序列问题
12.1.最长前缀 / 108
12.2.zipper / 110
12.3.最长公共子序列 / 111
12.3.1.动态规划算法一 / 112
12.3.2.动态规划算法二 / 115
12.4.确定基因功能 / 115
12.5.最长公共上升子序列 / 118
12.5.1.基本算法 / 119
12.5.2.优化算法 / 120
12.6.拓展与练习 / 122
第 13章 双重动态规划
13.1.城市交通 / 123
13.2.复杂的审批 / 126
13.3.拓展与练习 / 128
第 14章 多进程动态规划
14.1.方格取数 / 129
14.2.三取方格数 / 132
14.3.拓展与练习 / 134
第 15章 树形动态规划
15.1.加分二叉树 / 135
15.2.宝藏 / 137
15.3.选课 / 141
15.4.没有上司的舞会 / 144
15.5.拓展与练习 / 146
第 16章 数位动态规划
16.1.包含49 / 147
16.2.幸运数字 / 152
16.3.拓展与练习 / 155
第 17章 状态压缩动态规划
17.1.混乱的队伍 / 156
17.2.放置猛兽一 / 158
17.3.放置猛兽二 / 160
17.4.炮兵阵地 / 162
17.5.清扫计划 / 164
17.6.拓展与练习 / 166
第 18章 动态规划的高级优化
18.1.单调队列优化 / 167
18.1.1.最大子序列和 / 167
18.1.2.烽火传递 / 169
18.1.3.多重背包 / 171
18.1.4.纪念手表 / 174
18.2.四边形不等式优化 / 175
18.2.1.归并石子3 / 175
18.2.2.破坏铁路 / 178
18.2.3.分段 / 179
18.3.斜率优化 / 180
18.4.拓展与练习 / 184
第 19章 综合训练
19.1.逢低吸纳 / 185
19.2.红牌 / 186
19.3.点菜 / 187
19.4.选数统计 / 187
19.5.乌龟棋 / 188
19.6.守望者的逃离 / 189
19.7.三角形最大面积 / 190
19.8.积木游戏 / 191
19.9.多米诺骨牌 / 192
19.10.最大子树和 / 193
19.11.访问美术馆 / 194
19.12.花园 / 194
19.13.旅行计划 / 195
19.14.垃圾井 / 196
19.15.重建道路 / 197
19.16.迎接仪式 / 198
19.17.棋盘制作 / 199
19.18.打砖块 / 200
19.19.血缘关系 / 201
19.20.集合方案数 / 202
19.21.基因序列 / 203
19.22.基因武器 / 204
19.23.压路机 / 204
19.24.旅行商 / 206
19.25.二叉苹果树 / 207
19.26.技能树 / 208
19.27.骑士 / 209
19.28.猛兽动物园 / 210
