区间DP阶段性总结

MujinH · 2023-12-11 18:27:06 · 个人记录

最近练了区间dp，在这里做一些阶段性总结。

首先，区间dp是基于区间去进行转移的一种动态规划，区间dp的难点在于设状态与方程转移，题目一般不会把难点放在建模上，一般区间dp的题都能一眼看出。

区间dp的一般方程形式：dp[i][j]表示区间i到j的价值或花费。

一般题用这种状态信息量就够了，不够的话就再加一维，可以再加一维限制让状态信息更多。

然后是代码实现：

    for(int len=1;len<=n;len++){//枚举区间长度
        for(int i=1;i+len-1<=n;i++){//枚举左端点
            int j=i+len-1;//右端点
            //dp[i][j]
        }
    }

接着考虑转移，转移往往是题目的难点所在，区间dp难题的转移往往需要分类讨论，并且分叉很多。这里再提一句，如果是最小、最大价值（花费）类问题，方程就算重复讨论也不会出现问题，但计数类问题会更复杂些，要保证每种情况不重不漏地讨论到，计数类的区间dp往往也让人头疼。

转移一般分为两种，普通转移和题目操作转移。

普通转移：枚举断点，用两个小区间合并为大区间进行转移。
以计数为例：dp[i][j]=dp[i][k]+dp[k+1][j] (i<=k<j)

题目操作转移也比较难，根据题目而定。

最后是dp的优化，首先是四边形不等式优化 ，但比较难，就不在这里叙述。 还有一个前缀和优化 ，利用区间本身可以用前缀和表示的性质进行优化，往往是一边转移一边更新前缀和，优化效果大概能优化掉一个 n。

总体来说，区间dp的难度体现在状态与方程部分，当然也有建模难的，例如守卫 ，利用斜率的单调性进行建模。