区间DP总结

标签： 总结

---

序

总结一下区间DP的解题套路吧。

核心思想

区间DP顾名思义是通过以“区间”来进行转移。主要是通过小区间合并成大区间，最终得到全局的最优值。一般来说，这类DP具有比较明显的“区间性”，即可以选择区间这个状态进行转移，并且不同区间转移会获得不同的结果。
（口胡成分较多，可以忽略上述描述….）。

转移类型

因为是区间DP，所以肯定需要二维来存储区间状态：
$dp[i][j]$表示从i到j的最优值（当然通常是这样的，对于不同的题目我们也需要增加其他状态，这就需要我们仁者见仁了。）
下面来说说常见的几种转移类型：

1.枚举断点型

这类DP主要是可以通过划分不同的断点，来得到不同的值。他们彼此之间的小区间是互不关联的，$[i,j]$可以划分为$[i,k]$和$[k,j]$,并且这两段小区间不会相互影响。经典题目就是石子合并，能量项链等等。
代码模板：

for(int len = 1; len <= n; len ++) //枚举长度
    for(int i = 1; i <= n - len + 1; i ++) //枚举起点
    {
        int j = i + len - 1;//得到终点
        for(int k = i; k < j; k ++) //枚举断点
            f[i][j] = max(f[i][j], f[i][k] + f[k][j] +...); //转移
    }

那么推荐题目：
[USACO16OPEN]248
Outer space invaders
[HAOI2008]玩具取名

2.逐个转移类

这类DP主要是挨个挨个转移，也像是由小区间慢慢延伸到大区间。由$[i+1,j]$转移到$[i,j]$或者$[i,j+1]$转移到$[i,j]$。这类题目的性质可能是涉及区间的嵌套问题，不能通过枚举断点来实现；或者是逐个转移时候转移方程比较简单，容易实现；或者是题目描述具有较强的“单个操作”这类意思。
代码模板:

for(int len = 2; len <= n; len ++)
    for(int l = 1; l <= n - len + 1; l ++)
    {
        int r = l + len - 1;
        f[i][j] = max(f[i][j], f[i + 1][j] + ...)    
    }

经典题目有：括号匹配，最长回文子序列等。
推荐题目：
Palindrome subsequence

3.整体划分型

感觉这类DP题意比较明显，一般是给你一段区间，然后给你一种操作，然后用这种操作把区间划分成m段小区间，然后得到某种权值.
这类DP状态设计与前面有所不同:
$dp[i][j]$表示前i个元素划分成j段的最优值,通常是这样转移:

for(int i = 1; i <= n; i ++) //枚举长度 
    for(int j = 1; j <= m; j ++) //枚举划分段数 
        for(int k = 1; k < i; k ++) //枚举划分点 
            dp[i][j] = max(dp[i][j], dp[k][j - 1] + value(k+1,i))

经典题目：乘积最大,hdu3480 Division（需要用四边形不等式）
当然，上面的解法并不是独立的，有的题目可能使得上述解法相互嵌套，比如此题：String painter。而且区间DP的解法也不仅限于上述解法，还有许多精巧的DP思想和方程（如：USACO16OPEN 262144），这就需要多多积累构造方程的思想了。

四边形不等式

提到区间DP，肯定也要介绍一下关于它的优化——四边形不等式。不过博主才疏学浅（low得一逼），实在是没有怎么学好这个思想，只会套套板子，这里就无法进行总结，只能贴个链接了：四边形不等式

最后的话

总结解题套路是为了加强对这个DP思想的理解，但是却不能被固有的思想禁锢，DP这类题目是灵活多变的，遇到题目还是得分析题目性质，思考如何表示状态，如何转移。