信息学竞赛宝典 动态规划

● 难得一见的动态规划算法专项训练书 ● 直接以各类竞赛真题入手 ● 配有 PPT+ 源码 + 讲解视频 ● 提供对应在线题库 1.代码精炼、语言简练、内容全面、擅长将复杂的算法思想用浅显的图文形式描述。 2.讲解细致，关键代码有注释，有行号便于教师讲解，采用专业等宽编程字体，对初学者易犯的错误有提醒。 3.注重思维训练，一题多解，培养用数学思维解题。 4.全套经过多次校验过的精练代码参考及测试数据。 5.配有视频讲解，完整展示解题过程。 6.作者在算法竞赛领域有着多年的积累。

动态规划（Dynamic programming，DP；简称动规）在算法竞赛中占据极其重要的位置，也是初学者在刚接触算法设计时难以理解的知识点。简单来说，动态规划是一种用来解决最优化问题的算法思想，将一个复杂的问题分解成若干个子问题，通过综合子问题的最优解来得到原问题的最优解，通常适用于解决有重叠子问题和最优子结构性质的问题。
为了帮助初学者理解动态规划，本书直接以各类竞赛真题入手，全面细致地介绍算法竞赛中经常用到的各类动态规划算法模型，并精挑细选、由浅入深地安排了相关习题。
本书可以作为《信息学竞赛宝典基础算法》的进一步学习资料，也可以供有一定编程基础的读者作为学习动态规划算法的独立用书。

张新华 中学高级教师，信息学竞赛教练。取得浙江大学计算机科学与技术学士学位、厦门大学软件工程硕士学位，获得 2009年普通高中信息技术现场优质课比赛全国一等奖。培养的学生多次获得全国青少年奥林匹克联赛国家一等奖及亚太与太平洋地区信息学奥林匹克竞赛奖牌。著有“信息学竞赛宝典”系列书。开发了三维图形化 C++ 编程工具 Dev-C++ 智能开发平 台和 Python 可视化界面设计软件 Visual Python。 胡向荣 安徽省信息学竞赛金牌教练。获得中国首届网络管理员大赛亚军，安徽省首届计算机技术大赛一等奖，安徽省信息技术优质课评选一等奖。安庆市教育技术专家、信息技术学科骨干教师、先进教研个人。 伍婉秋 初中信息技术一级教师，广州市白云区永平片初二信息技术教研组组长；参与教育部全国教育科学“十三五”规划课题“三维图形化智能编程系统在中小学编程教育中的构建和应用”；曾获广州市中学信息技术教师教学能力比赛二等奖、白云区一等奖。

第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