区间DP&环形DP

· · 算法·理论

区间DP是啥？

就是一种高级的DP。先看例题：

1. 区间DP例题：合并石子

按照之前的DP，很容易想到定义 f_i 表示堆前 i 个的最优解。但这行得通吗？
可以想到，f_{i\sim j} 是没法维护的（只维护了前缀），故定义 f_{i,j} 表示第 i 到 j 个的最优解。
我们知道，合并 i\sim j，是需要先计算出所有 i\sim k,k\sim j 的答案。而如果只写：

for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)

是无法保证长度的。
所以先枚举长度

for(int l=2;l<=n;l++)
    for(int i=1;i+l-1<=n;i++)
    {
        int j=i+l-1;
        DP;
    }

接着，计算最优解。

for(int l=2;l<=n;l++)
    for(int i=1;i+l-1<=n;i++)
    {
        int j=i+l-1,s=sum[j]-sum[i-1];
        for(int k=i;k<j;k++)
            dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+s);
    }

时空复杂度很简单：分别是 O(n^3),O(n^2)。

所以区间DP是啥呢？就是求区间最优解。他需要长度从小到大才能维护。

2. 环形DP例题：石子合并

题意不变，只是改成了一圈。
如果将 a_i 复制一遍，即 a_i=a_{i-n}，就可以看成是 n 个。这 n 个区间就是环的 n 种展开方式。
即先复制，再DP。

环形DP核心：复制。

3. 搞基环形DP

但环形DP必须复制吗？比如这道题：诗意
可以复制，但还有更简单的办法。
如果记 s=\sum a_i，如果 x=\sum\limits^r_{l=1} a_i 是能截取的到的最小区间，那么最大的一定是 s-x。
故 O(n) 解决（孑孓）。