浅谈区间DP

本篇随笔浅谈一下DP中的区间DP。

一、区间DP的概念

在算法竞赛中，有很多数据结构、算法其实是比较相通的。所以类比一下其实也不是很过分。

但是其中必定蕴含着些许不同。而这种不同就是我们需要品味和体会的了。

比如线段树。

在本蒟蒻的大力理解下，我把它类比成区间DP+树形DP。

你看，它的每个节点维护的一个区间信息，然后按二叉树的形态，每个节点的信息由子节点推出，一层层向上递归，最终到达根节点。

但是它和区间DP尚有不同。

区间DP又类似于弗洛伊德Floyd算法。

也就是枚举断点，更新区间。

区间DP的状态一般是：

(dp[i][j])表示从i到j这个区间的某个信息。

然后转移方程一般都是：

[dp[i][j]=max(dp[i][j],dp[i][k]+dp[k+1][j]+calc()) ]

其中，k是断点，calc()是计算更新信息的方式。

也就是说，区间DP的阶段划分是区间长度，每个区间是由比它更短的区间更新而来的。

二、区间DP的模板和复杂度分析

刚刚已经讲过了，区间DP的阶段划分是区间长度，我们需要保证长度较短的区间全部处理完之后，再处理长度比较长的区间。所以最外层循环就需要枚举区间长度。

然后就是枚举区间左右端点了。但是因为外面的区间长度，所以右端点只需要通过左端点算出来就行，不用枚举。

所以大体代码就是这样的：

for(int len=2;len<=n;len++)
        for(int i=1;i<=2*n-len+1;i++)
        {
            int j=i+len-1;
            for(int k=i;k<j;k++)
                dp[i][j]=max(dp[i][j],dp[i][k]+dp[k+1][j]+calc());
        }

当然，也有枚举时比这份代码多了+1-1之类的版本。实际意义是一样的。大家挑自己喜欢的即可。

通过以上代码，我们清楚：区间DP的时间复杂度是(O(n^3))的