dp动态规划分类详解

转自

 

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

 

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

动态规划（：Dynamic programming，DP）是一种在、和中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。 动态规划常常适用于有和性质的问题，动态规划方法所耗时间往往远少于朴素解法。

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

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

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

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

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

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

 

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

一、简单基础dp

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

1、递推：

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

简单:

 简单从上往下递推

 简单递推计数

 简单递推计数（Fibonacci）

 Fibonacci

 找递推公式

推荐：

 四个角递推

 带限制条件的计数递推dp

 同上题

2、背包

经典的背包九讲：

推荐博客：

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

简单：

 01背包

 01背包

 01背包

 多重背包

 完全背包

推荐：

  转化成背包

 转化成背包

 状压+背包

 带限制条件的背包

背包的转化成组合数学

 转化成完全背包问题

 扩大区间+输出路径

 图论+背包

3、LIS

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

简单：

推荐：

 LCS转化成LIS

　数位dp+LIS思想

 状态压缩+LIS

 两次dp

4、LCS

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

 要先排个序

 

二、区间dp

推荐博客：

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

 括号匹配并输出方案

 转化成求回文串 

 贪心+区间dp

  常见写法

 

 

三、树形dp

比较好的博客：

一篇论文：

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

 二分+树形dp+单调队列

  求树的直径

 

 思维

 MST+树形dp 比较经典

 MST+树形dp 同上

 有点像对抗搜索

 树直径的思想 思维

 搜两遍

 

四、数位dp

推荐一篇论文：

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

 简单数位dp

 比较简单

 状压+数位dp

 把模数加进状态里面

 简单数位dp

 思维变换的数位dp

　数位dp+LIS思想

  比较巧妙的数位dp

 比较难想

 数位dp+组合数学+逆元

 

五、概率(期望) dp

推荐博客：

推荐博客：

推荐论文：

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

 比较基础

 比较经典BFS+概率dp+高斯消元

 推公式比较水

 

 高斯消元+概率dp+BFS预处理

 简单概率dp

 简单概率dp,比较直接

 比较经典

 题目比较难读懂

 从后往前，比较简单

 经典好题，借助树的概率dp

 状态压缩+概率dp

 这个题状态有点难抽象

 

六、状态压缩dp

这类问题有TSP、插头dp等。

推荐论文：

推荐博客：

推荐博客：

 最短路+TSP

 插头dp

 轮廓线dp

 

七、优化的dp

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

1、二进制优化

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

 

2、单调队列优化

推荐论文：

推荐博客：

 

 二分+单调队列优化

3、斜率优化

推荐论文：

推荐博客：

4、四边形不等式优化

推荐博客：

推荐博客：