区间DP

什么是区间 DP

区间类动态规划是线性动态规划的扩展，它在分阶段地划分问题时，与阶段中元素出现的顺序和由前一阶段的哪些元素合并而来有很大的关系。令状态$f_{i,j}$表示将下标位置$i$到$j$的所有元素合并能获得的价值的最大值，那么 ，$max(f_{i,k}+f_{k+1,j}+cost)$为将这两组元素合并起来的代价。

区间 DP 的特点：

合并：即将两个或多个部分进行整合，当然也可以反过来；

特征：能将问题分解为能两两合并的形式；

求解：对整个问题设最优值，枚举合并点，将问题分解为左右两个部分，最后合并两个部分的最优值得到原问题的最优值。

实现方式

1.迭代式

1
2
3
4
5
6
7
8
9

for(int len=2;len<=n;len++){
    for(int l=1;l<=n-len+1;l++){
        int r=l+len-1;
        for(int k=l;k<r;k++){
            f[l][r]=max/min (f[l][r],f[l][k]+f[k+1][r]+a[i]);
        }
    }
}
cout<<f[1][n]

2.记忆化搜索

破环为链

详情见石子合并

先设sum[i]表示从1~i的前缀和

如果石堆排成一排

那么显然有转移方程

但是我们观察这道题可以发现，由于这些石堆不是一个圈，而是一条链，那么我们考虑：

1.朴素做法：让每一个点都成为第一个点，然后逐次试一试 (时间复杂度：$O(N^4)$)

2.破坏为链：先将这个链拆开，然后复制一下这条链，首连尾粘贴到链的一端

就大概长成这样（画的好丑啊

时间复杂度：$O(n^3)$

高精度区间DP