信息学竞赛宝典 动态规划

图书标准信息

• 作者 张新华 胡向荣 伍婉秋
• 出版社 人民邮电出版社
• 出版时间 2024-02
• 版次 1
• ISBN 9787115620361
• 定价 69.90元
• 装帧 平装
• 开本 16开
• 页数 224页
• 字数 320千字

【内容简介】

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

【作者简介】

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

【目录】

章 长不下降子序列问题

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

0章  优选连续子序列问题

10.1.优选连续子序列和 97

10.2.优选连续子序列积 98

10.3.k个优选连续子序列和 99

10.4.拓展与练 101

1章  子矩阵问题

11.1.二维优选子矩阵问题 102

11.2.扩展优选子矩阵问题 104

11.3.子矩阵变形问题 105

11.4.拓展与练 107

2章  子序列问题

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

3章  双重动态规划

13.1.城市交通 123

13.2.复杂的审批 126

13.3.拓展与练 128

4章  多进程动态规划

14.1.方格取数 129

14.2.三取方格数 132

14.3.拓展与练 134

5章  树形动态规划

15.1.加分二树 135

15.2.宝藏 137

15.3.选课 141

15.4.没有上司的舞会 144

15.5.拓展与练 146

6章  数位动态规划

16.1.包含49 147

16.2.幸运数字 152

16.3.拓展与练 155

7章  压缩动态规划

17.1.混乱的队伍 156

17.2.放置猛兽一 158

17.3.放置猛兽二 160

17.4.炮兵阵地 162

17.5.清扫计划 164

17.6.拓展与练 166

8章  动态规划的优化

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

9章  综合训练

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