【动态规划总结】

11-25 1,366 views

最近一直在做dp的题。做了有不少题吧。没什么难度。简单的做一下总结。

题目大都做的 网上的 【46道dp训练计划

第一类—背包类dp


 

背包还是算是最基础的问题了。(有一个背包九讲

自己做的时候也就遇到了4种。

1. 完全背包.

完全背包一般是所有东西都是不限数量随意用的。这个也比较简单了。 我比较习惯滚动数组,到达某个状态的最优解。

这个一般是两层循环,都是正推,因为正推可以满足无限使用的条件。

训练题目:HDU 2955 Robberies   题解在这

2. 01背包.

01 背包一般是所有东西都只能最多使用一次。也就出现了用或者不用的时候 到达某个状态的最优解。

这个一般是两层循环,外层是商品的属性(正推),内层是状态(逆推)。只有状态逆推才能保证使用一次。这也是和完全背包最大的不同之处。

训练题目:HDU 1864 最大报销额  题解在这   HDU 2602 Bone Collector 题解在这

3.二维背包.

二维背包一般就是两种状态了。完全背包,01背包都是可以写成一维滚动数组的。 二维背包无非就是两种属性了。所以用二维来保存一种状态的最优解。

还是那样。 如果某个属性是 01背包。就逆推。 如果是 完全背包是正推。

训练题目:HDU 2159 FATE 题解在这

4.多重背包.

在没有做训练计划之前。没有接触过多重背包。多重背包的特点是。某一个商品 给定了特定的数量。

它不像完全背包。 可以无穷的使用。 也不像 01背包一样 用或者不用。 这个在于用几个的问题。

最初自己做题的时候的想法是把这些数量平摊开成 n 个新商品。 但是明显的会超时。 所以看了背包九讲之后就明白多了。

对于一些数量很多达到最大状态的就可以当做完全背包来处理。 对于一些数量比较少的。 那就需要用二进制来优化,然后当做01背包来处理(详情参照背包九讲)

训练题目:HDU 2844 Coins 题解在这    HDU 1059 Dividing   题解在这 HDU 2191 珍惜现在,感恩生活 题解在这

第二类—最大连续和


 

最大连续和也算是最简单,最基本的动态规划问题了。 自己碰见的有两类。

1. 直接求最大连续和.

没什么好说的,直接求就好了。。

训练题目:HDU 1231 最大连续和 题解在这

2. 多个子段和的最大和。

问题就是。对于一个序列。 求出 m 组 不相交的子段,使得其和最大。 这个问题想了好几天。最后还是看了解题报告才想明白。

自己写的时候一直忽略了一个问题。就是 到达某个状态的时候 一定是要以这个元素为结尾的子段(这个元素和前面连成一段或者单独成段)。那么久好写了。

训练题目:HDU 1024 MAX SUM PLUS PLUS  题解在这

第三类—某个元素在一段连续序列内为最小值/最大值


 

这类题的意思是。我们通常在解决问题的过程中,需要知道某一个元素是在包含自身的一段连续序列为最小值

如果使用RMQ虽然是可以的。 但是需要枚举左右边界,复杂度还是高。

1.一维的。

这个题主要思想就是递推。 比如序列  5 4 3 4 5   ,4所在的范围就是5 4.  我们在求3的左边界的时候,如果3左边的元素大于3的话,那么该元素的边界一定也是3的,

这样地推出左边界, 右边界同理可以求出。 然后就知道 某个元素的左右边界了。

训练题目:HDU 1506 Largest Rectangle in a Histogram  题解在这

2.二维的。

二维的思想和一维差不多。 直接上题目吧

训练题目:HDU 1505City Game 题解在这 

第四类—数塔问题


 

数塔问题也就是 对于一个三角形/ 矩阵 形状的数字。 对于每一个位置,每次都往左或者往右转移, 直到底端求最大和这样的问题。

HDU 1176 免费馅饼  题解在这

第五类—最大上升子序列(LIS)


 

在一个序列中找一个最大上升子序列的长度。

有最朴素的动规方法,n^2的复杂度。有些题还是可以承受,但是数据量一大就承受不了了。

还有一种 nlogn 的方法。 就比较奇妙了~ 用的是扫一遍加二分。

训练题目:uva 10534 Wavio Sequence  题解在这   还有一些比较好的变形:HDU 1160 FatMouse’s Speed 题解在这  HDU 1025 Constructing Roads In JGShining’s Kingdom 题解在这

第五类—状态压缩dp


 

这个自己练的也不是很多。也不熟。基本想法还有一点。就是在数据比较小的时候。 比如10 15这样的数量的东西。 有顺序问题的时候。 就可以用二进制来解决。

每一个二进制都保存的一个状态。 比如  111 这个状态 就可以由 110 011  101 来转移…… 这样。 有这个基本思路就好解决了。

训练题目:HDU 1074 Doing Homework 题解在这 ZOJ 3802   Easy 2048 Again  题解在这 HDU 5045 Context 题解在这

第六类—输出路径


 

这种题目其实主要的还是求状态转移方程。状态转移方程出来了。一般这个题就没有问题了。 路径输出还是按照最优的路径来解决的。

我一般比较喜欢在 状态转移的时候 加一个数组 fa 来表示这个节点的 父节点。 然后递归输出。

训练题目:UVA 10453 Make Palindrome 题解在这  HDU 5092 Seam Carving  题解在这  UVA 10564 – Paths through the Hourglass  题解在这

其他类—好题集锦


 

1.HDU 4991 Ordered Subsequence(dp+树状数组) 状态转移方程好写。但是一看就超时。需要用数据结构优化。 题解在这

2.HDU 2059 龟兔赛跑  这个题虽然也挺水。但是自己思路确实没有想到这一步。 感觉这题不错。 题解在这

3.UVA 10817 Headmaster’s Headache(位运算模拟子集+dp) 二进制枚举子集。 然后dp。 题解在这

 

持续更新。

「中国软件杯」总结

1.比赛的初衷 参加这次比赛,本来是没有抱着很大的期望能拿什么大奖的,而是抱着一颗学习新技能的心态来参加的。 不过最终进入了全国总决赛,算是意外之喜,...

阅读全文

baidu「周总结」

一.学习 这周相对来说比较充实,主要是了解贴吧的架构,导师给的问题又比较好,所以我顺藤摸瓜,去学习就行。 这周学习总体来说还是以nginx为主线进行延伸的...

阅读全文

baidu「day3」

昨天回家里,遇到各种问题,忘了写总结啦,今天补上 一.学习 1.1 今天自己搭建了一个项目,然后在浏览器上跑起来了~挺好的~ 1.2 当我们在浏览器请求一个url的...

阅读全文

欢迎留言

*