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

张新华，中学高级教师，信息学竞赛教练，长期从事中小学信息学竞赛辅导工作。取得浙江大学计算机科学与技术学士学位、厦门大学软件工程硕士学位，获得2009年普通高中信息技术现场优质课比赛全国一等奖。培养的学生多次获得全国青少年信息学奥林匹克联赛国家一等奖及亚洲与太平洋地区信息学奥林匹克竞赛奖牌。著有《编程竞赛宝典》。开发的软件有三维图形化C++编程工具Dev-C++智能开发平台和Python可视化界面设计软件Visual Python。

第1章 最长不下降子序列问题
1.1 最长不下降子序列
1.2 抄近路
1.3 宝藏
1.4 导弹拦截
1.5 和谐俱乐部
1.6 滑雪
1.7 拓展与练习
第2章 背包问题
2.1 简单背包问题
2.2 0/1背包问题
2.3 0/1背包算法的优化
2.4 分组背包问题
2.4.1 二维数组动态规划算法
2.4.2 一维数组优化算法
2.5 拓展与练习
第3章 完全背包问题
3.1 完全背包
3.2 完全背包算法的优化
3.3 拓展与练习
第4章 多重背包问题
4.1 多重背包
4.2 通天塔
4.3 忙碌
4.4 拓展与练习
第5章 二维费用背包问题
5.1 训练赛
5.2 电脑游戏
5.3 拓展与练习
第6章 区间动态规划
6.1 书架问题1
6.2 书架问题2
6.3 收购珍珠
6.4 双色马
6.5 归并石子1
6.6 切割铜棒
6.7 邮局问题
6.8 乘积最大
6.9 凸多边形三角划分
6.10 凸多边形分割
6.11 拓展与练习
第7章 路径问题
7.1 最短路径
7.2 最少交通费用问题
7.3 拓展与练习
第8章 资源类动态规划
8.1 机器分配
8.2 调度问题
8.3 系统可靠性
8.4 购物
8.5 快餐问题
8.6 拓展与练习
第9章 动态规划的简单优化
9.1 丝绸之路
9.1.1 动态规划算法一
9.1.2 动态规划算法二
9.1.3 动态规划算法三
9.2 双人游戏
9.2.1 动态规划算法一
9.2.2 动态规划算法二
9.3 理想收入问题
9.3.1 朴素算法
9.3.2 优化算法一
9.3.3 优化算法二
9.3.4 优化算法三
9.3.5 优化算法四
9.3.6 贪心算法
9.4 唱片录制
9.4.1 动态规划算法一
9.4.2 动态规划算法二
9.4.3 动态规划算法三
9.5 相遇问题
9.5.1 动态规划算法
9.5.2 普通递归算法
9.5.3 优化递归算法
9.5.4 宽度优先搜索算法
9.5.5 动态规划算法的优化
9.6 拓展与练习
第10章 最大连续子序列问题
10.1 最大连续子序列和
10.2 最大连续子序列积
10.3 k个最大连续子序列和
10.4 拓展与练习
第11章 子矩阵问题
11.1 二维最大子矩阵问题
11.2 扩展最大子矩阵问题
11.3 子矩阵变形问题
11.4 拓展与练习
第12章 子序列问题
12.1 最长前缀
12.2 zipper
12.3 最长公共子序列
12.3.1 动态规划算法一
12.3.2 动态规划算法二
12.4 确定基因功能
12.5 最长公共上升子序列
12.5.1 基本算法
12.5.2 优化算法
12.6 拓展与练习
第13章 双重动态规划
13.1 城市交通
13.2 复杂的审批
13.3 拓展与练习
第14章 多进程动态规划
14.1 方格取数
14.2 三取方格数
14.3 拓展与练习
第15章 树形动态规划
15.1 加分二叉树
15.2 宝藏
15.3 选课
15.4 没有上司的舞会
15.5 拓展与练习
第16章 数位动态规划
16.1 包含
16.2 幸运数字
16.3 拓展与练习
第17章 状态压缩动态规划
17.1 混乱的队伍
17.2 放置猛兽一
17.3 放置猛兽二
17.4 炮兵阵地
17.5 清扫计划
17.6 拓展与练习
第18章 动态规划的高级优化
18.1 单调队列优化
18.1.1 最大子序列和
18.1.2 烽火传递
18.1.3 多重背包
18.1.4 纪念手表
18.2 四边形不等式优化
18.2.1 归并石子
18.2.2 破坏铁路
18.2.3 分段
18.3 斜率优化
18.4 拓展与练习
第19章 综合训练
19.1 逢低吸纳
19.2 红牌
19.3 点菜
19.4 选数统计
19.5 乌龟棋
19.6 守望者的逃离
19.7 三角形最大面积
19.8 积木游戏
19.9 多米诺骨牌
19.10 最大子树和
19.11 访问美术馆
19.12 花园
19.13 旅行计划
19.14 垃圾井
19.15 重建道路
19.16 迎接仪式
19.17 棋盘制作
19.18 打砖块
19.19 血缘关系
19.20 集合方案数
19.21 基因序列
19.22 基因武器
19.23 压路机
19.24 旅行商
19.25 二叉苹果树
19.26 技能树
19.27 骑士
19.28 猛兽动物园