爱悠闲 > 【DP专辑】ACM动态规划总结

【DP专辑】ACM动态规划总结

分类: 动态规划  |  作者: cc_again 相关  |  发布日期 : 2014-06-09  |  热度 : 908°

动态规划一直是ACM竞赛中的重点,同时又是难点,因为该算法时间效率高,代码量少,多元性强,主要考察思维能力、建模抽象能力、灵活度。

本人动态规划博客地址:http://www.aiuxian.com/catalog/p-76943.html

******************************************************************************************

动态规划英语Dynamic programming,DP)是一种在数学计算机科学经济学中使用的,通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。 动态规划常常适用于有重叠子问题最优子结构性质的问题,动态规划方法所耗时间往往远少于朴素解法。

动态规划背后的基本思想非常简单。大致上,若要解一个给定问题,我们需要解其不同部分(即子问题),再合并子问题的解以得出原问题的解。 通常许多子问题非常相似,为此动态规划法试图仅仅解决每个子问题一次,从而减少计算量: 一旦某个给定子问题的解已经算出,则将其记忆化存储,以便下次需要同一个子问题解之时直接查表。 这种做法在重复子问题的数目关于输入的规模呈指数增长时特别有用。

动态规划问题满足三大重要性质

最优子结构性质:如果问题的最优解所包含的子问题的解也是最优的,我们就称该问题具有最优子结构性质(即满足最优化原理)。最优子结构性质为动态规划算法解决问题提供了重要线索。

子问题重叠性质:子问题重叠性质是指在用递归算法自顶向下对问题进行求解时,每次产生的子问题并不总是新问题,有些子问题会被重复计算多次。动态规划算法正是利用了这种子问题的重叠性质,对每一个子问题只计算一次,然后将其计算结果保存在一个表格中,当再次需要计算已经计算过的子问题时,只是在表格中简单地查看一下结果,从而获得较高的效率。

无后效性将各阶段按照一定的次序排列好之后,对于某个给定的阶段状态,它以前各阶段的状态无法直接影响它未来的决策,而只能通过当前的这个状态。换句话说,每个状态都是过去历史的一个完整总结。这就是无后向性,又称为无后效性。

********************************************************************************************


动态规划分类有很多划分方法,网上有很多是按照状态来分,分为一维、二维、区间、树形等等。我觉得还是按功能即解决的问题的类型以及难易程度来分比较好,下面按照我自己的理解和归纳,把动态规划的分类如下:

一、简单基础dp

这类dp主要是一些状态比较容易表示,转移方程比较好想,问题比较基本常见的。主要包括递推背包LIS(最长递增序列)LCS(最长公共子序列),下面针对这几种类型,推荐一下比较好的学习资料和题目。

1、递推:

递推一般形式比较单一,从前往后,分类枚举就行。

简单:

hdu 2084 数塔 简单从上往下递推

hdu 2018 母牛的故事 简单递推计数

hdu 2044 一只小蜜蜂... 简单递推计数(Fibonacci)

hdu 2041 超级楼梯 Fibonacci

hdu 2050 折线分割平面 找递推公式

推荐:

http://www.aiuxian.com/article/p-938768.html 四个角递推

http://www.aiuxian.com/article/p-938740.html 带限制条件的计数递推dp

http://www.aiuxian.com/article/p-938741.html 同上题

http://www.aiuxian.com/article/p-555678.html

http://www.aiuxian.com/article/p-555861.html

http://www.aiuxian.com/article/p-555656.html

2、背包

经典的背包九讲:链接地址

推荐博客:http://www.aiuxian.com/article/p-693934.html

主要有0-1背包完全背包分组背包多重背包

简单:

hdu 2955 Robberies 01背包

hdu 1864 最大报销额 01背包

hdu 2602 Bone Collector 01背包

hdu 2844 Coins 多重背包

hdu 2159 FATE 完全背包

推荐:

http://www.aiuxian.com/article/p-555754.html  转化成背包

http://www.aiuxian.com/article/p-555754.html 转化成背包

http://www.aiuxian.com/article/p-555698.html 状压+背包

http://www.aiuxian.com/article/p-938778.html 带限制条件的背包

zoj 3638 Fruit Ninja 背包的转化成组合数学

http://www.aiuxian.com/article/p-555662.html 转化成完全背包问题

http://www.aiuxian.com/article/p-938758.html 扩大区间+输出路径

http://www.aiuxian.com/article/p-555640.html 图论+背包

3、LIS

最长递增子序列,朴素的是o(n^2)算法,二分下可以写成o(nlgn):维护一个当前最优的递增序列——找到恰好大于它更新

简单:

hdu 1003 Max Sum

hdu 1087 Super Jumping!

推荐:

http://www.aiuxian.com/article/p-555745.html LCS转化成LIS

http://www.aiuxian.com/article/p-555672.html 数位dp+LIS思想

http://www.aiuxian.com/article/p-555692.html 状态压缩+LIS

http://www.aiuxian.com/article/p-555699.html 两次dp

4、LCS

最长公共子序列,通常o(n^2)的算法

hdu 1503 Advanced Fruits

hdu 1159 Common Subsequence

http://www.aiuxian.com/article/p-555776.html 要先排个序

poj 1080 Human Gene Functions


二、区间dp

推荐博客:http://www.aiuxian.com/article/p-694020.html

区间dp,一般是枚举区间,把区间分成左右两部分,然后求出左右区间再合并。

http://www.aiuxian.com/article/p-555641.html 括号匹配并输出方案

http://www.aiuxian.com/article/p-555677.html 转化成求回文串 

http://www.aiuxian.com/article/p-555659.html 贪心+区间dp

poj 2955 Brackets

http://www.aiuxian.com/article/p-694021.html  常见写法

hdu 2476 String Printer 

zoj 3537 Cake

CF 149D Coloring Brackets

zoj 3469 Food Delivery


三、树形dp

比较好的博客:http://www.aiuxian.com/article/p-693940.html

一篇论文:链接地址

树形dp是建立在树这种数据结构上的dp,一般状态比较好想,通过dfs维护从根到叶子或从叶子到根的状态转移。

http://www.aiuxian.com/article/p-555686.html 二分+树形dp+单调队列

http://www.aiuxian.com/article/p-555805.html  求树的直径

http://www.aiuxian.com/article/p-555724.html 

http://www.aiuxian.com/article/p-555661.html 思维

http://www.aiuxian.com/article/p-555648.html

http://www.aiuxian.com/article/p-555688.html MST+树形dp 比较经典

http://www.aiuxian.com/article/p-555690.html MST+树形dp 同上

http://www.aiuxian.com/article/p-555707.html 有点像对抗搜索

http://www.aiuxian.com/article/p-555644.html 树直径的思想 思维

hdu 2196 Computer 搜两遍


四、数位dp

推荐一篇论文:链接地址

数位dp,主要用来解决统计满足某类特殊关系或有某些特点的区间内的数的个数,它是按位来进行计数统计的,可以保存子状态,速度较快。数位dp做多了后,套路基本上都差不多,关键把要保存的状态给抽象出来,保存下来。

hdu 2089 不要62 简单数位dp

hdu 3709 Balanced Number 比较简单

http://www.aiuxian.com/article/p-938745.html 状压+数位dp

http://www.aiuxian.com/article/p-555802.html 把模数加进状态里面

http://www.aiuxian.com/article/p-555669.html 简单数位dp

http://www.aiuxian.com/article/p-555703.html 思维变换的数位dp

http://www.aiuxian.com/article/p-555672.html 数位dp+LIS思想

http://www.aiuxian.com/article/p-555799.html  比较巧妙的数位dp

http://www.aiuxian.com/article/p-555801.html 比较难想

http://www.aiuxian.com/article/p-555803.html 数位dp+组合数学+逆元


五、概率(期望) dp

推荐博客:链接地址

推荐博客:http://www.aiuxian.com/article/p-694005.html

推荐论文:

《走进概率的世界》

《浅析竞赛中一类数学期望问题的解决方法》

《有关概率和期望问题的研究》

一般来说概率正着推,期望逆着推。有环的一般要用到高斯消元解方程。期望可以分解成多个子期望的加权和,权为子期望发生的概率,即 E(aA+bB+...) = aE(A) + bE(B) +... 

http://www.aiuxian.com/article/p-555817.html 比较基础

http://www.aiuxian.com/article/p-555655.html 比较经典BFS+概率dp+高斯消元

http://www.aiuxian.com/article/p-555654.html 推公式比较水

http://www.aiuxian.com/article/p-555862.html 

http://www.aiuxian.com/article/p-555710.html 高斯消元+概率dp+BFS预处理

http://www.aiuxian.com/article/p-555666.html 简单概率dp

http://www.aiuxian.com/article/p-555668.html 简单概率dp,比较直接

http://www.aiuxian.com/article/p-555652.html 比较经典

http://www.aiuxian.com/article/p-555864.html 题目比较难读懂

http://www.aiuxian.com/article/p-555665.html 从后往前,比较简单

http://www.aiuxian.com/article/p-555667.html 经典好题,借助树的概率dp

http://www.aiuxian.com/article/p-555660.html 状态压缩+概率dp

http://www.aiuxian.com/article/p-555653.html 这个题状态有点难抽象


六、状态压缩dp

这类问题有TSP插头dp等。

推荐论文:链接地址

推荐博客:链接地址

推荐博客:链接地址

http://www.aiuxian.com/article/p-555838.html

http://www.aiuxian.com/article/p-555872.html 最短路+TSP

http://www.aiuxian.com/article/p-555866.html 插头dp

http://www.aiuxian.com/article/p-555823.html

poj 1185 炮兵阵地

http://www.aiuxian.com/article/p-555837.html 轮廓线dp

hdu 3811 Permutation

poj 1038

poj 2441

hdu 2167

hdu 4026

hdu 4281


七、数据结构优化的dp

有时尽管状态找好了,转移方程的想好了,但时间复杂度比较大,需要用数据结构进行优化。常见的优化有二进制优化、单调队列优化、斜率优化、四边形不等式优化等。

1、二进制优化

主要是优化背包问题,背包九讲里面有介绍,比较简单,这里只附上几道题目。

hdu 1059 Diving 

hdu 1171 Big Event in Hdu

poj 1048 Follow My Magic

2、单调队列优化

推荐论文:链接地址

推荐博客:链接地址

http://www.aiuxian.com/article/p-555829.html 

http://www.aiuxian.com/article/p-555830.html 二分+单调队列优化

3、斜率优化

推荐论文:用单调性优化动态规划

推荐博客:链接地址

hdu 3507 Print Article

poj 1260 Pearls

hdu 2829 Lawrence

hdu 2993 Max Average Problem

4、四边形不等式优化

推荐博客:链接地址

推荐博客:链接地址

hdu 2952 Counting Sheep

poj 1160 Post Office

hdu 3480 Division

hdu 3516 Tree Construction

hdu 2829 Lawrence