书名：信息学竞赛宝典.动态规划
定价：69.9
ISBN：9787115620361
作者：张新华 胡向荣 伍婉秋
版次：第1版
出版时间：2024-02

内容提要：
动态规划（Dynamic Programming，DP；简称动规）在算法竞赛中占据极其重要的位置，也是初学者在刚接触算法设计时觉得难以理解的知识点。简单来说，动态规划是一种用来解决*化问题的算法思想，将一个复杂的问题分解成若干个子问题，通过综合子问题的*解来得到原问题的*解，通常适用于解决有重叠子问题和*子结构性质的问题。 为了帮助初学者理解动态规划，本书直接以各类竞赛真题入手，*细致地介绍算法竞赛中经常用到的各类动态规划算法模型。为了读者能更深刻地理解和掌握其算法思想内涵，本书精挑细选、由浅入深地安排了相关习题。



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

目录：
目录
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