信息学竞赛宝典：动态规划

封面

版权信息

版权

内容提要

本书编委会

前言

算法竞赛介绍

为什么要学习算法？

本书的特色及用法

拓展与练习说明

适合阅读本书的读者

致谢

最后要说的话

第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 子矩阵变形问题