区间DP
定义
区间类动态规划是线性动态规划的扩展，它在分阶段地划分问题时，与阶段中元素出现的顺序和由前一阶段的哪些元素合并而来有很大的关系。
令状态$f(l,r)$表示$l到r$ 的区间的元素合并能获得到的价值最大（最小），为此$f(l,r) = max{f(l,k)+f(k+1,r) + W}$,$W$为这两个区间合并起来的价值。
该问题的求解主要是通过合并小区间的最优解进而得出整个大区间的最优解。
特点
区间 DP 有以下特点：
合并：即将两个或多个部分进行整合，当然也可以反过来；
特征：能将问题分解为能两两合并的形式；
求解：对整个问题设最优值，枚举合并点，将问题分解为左右两个部分，最后合并两个部分的最优值得到原问题的最优值。
一般解法
- 一般第一层是枚举 $len$ 长度
- 第二层是枚举 $l$ 也就是左端点，然后 $r$ 可以通过 $l + len - 1$ 计算出来
- 第三层是枚举断点 $k$ 从 $l$ 到 $r$
经典题目
石子合并
经典思想: 拆环成链,通过复制数组的手段达到将一个环拆成链式的结构，方便求解。
解法
对于每一个区间 $(l,r)$ 我们可以通过 $k$ 将整个区间分为两块 $f(l,k),f(k+1,r)$ ，如果要求$(l,r)$ 这个区间的最大/最小值，对于任意两堆，我们可以直接把这两堆的和加上，作为一部分贡献W，但是可以发现，如果某一堆里面有多个数，我们不仅仅只加当前的值，还需要加上整个区间的区间和C。
对于我们区间$(l,r)$来说，我们每次合并所产生的值就为 $W + C$ 因为 $(l,r)$ 区间是固定的，所以能够变换的只有 $W$ 所以我们怎样求 $W$ 的最大/最小 又成了一个子问题。我们对于每一个区间 $(l,r)$ 会有大量的这样的重叠子问题，所以我们才会按照 $k$ 来将我们的区间划分为两部分。
例如这个样例
1 | |
图中表示的是最小值的合并方式，对于区间$(1,3)$ 来说我们可能还会由 $f(1,1),f(2,3)$ 这里便出现了重叠子问题。
最后：
当$l == r$ 单个位置得分为0：$f_{len,l,r} = 0$
当 $l \neq r$
- 计算最大值的转移：$f_{len,l,r}=max(f_{k−l+1,l,k}+f_{len−(k−l+1),k+1,r}+cost_{l,r})$ $(l \leq k \lt r)$
- 计算最小值的转移：$f_{len,l,r}=min(f_{k−l+1,l,k}+f_{len−(k−l+1),k+1,r}+cost_{l,r})$ $(l \leq k \lt r)$
P1880 [NOI1995] 石子合并 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
平行四边形优化
因为我们普通的区间DP时间复杂度是 $O(n^3)$ 但是我们状态转移方程又设计好了，怎么去优化呢？
动态规划优化与四边形不等式
有方程：$f(i,j) = \min(f(i,k) + f(k+1,j) + w(i,j)), s(i,j)$ 为最优点取到值。
四边形不等式
如果函数 $w$ 满足以下不等式：
$$
f(i, j) + f(i’, j’) \leq f(i’, j) + f(i, j’)
$$
那么我们称函数 $w$ 满足四边形不等式。这个性质对于优化动态规划算法非常重要。
平行四边形优化
在满足四边形不等式的情况下，我们可以利用以下性质来加速计算：
$$
s(i, j-1) \leq s(i, j) \leq s(i + 1, j)
$$
其中，$s(i,j)$ 是计算过程中记录的最优分割点。这个优化思想利用了平行四边形不等式来减少不必要的计算，从而提高了算法的效率。
算法改动
添加 $s(i,j)$ 数组：记录在计算 $f(i,j)$ 时的最优分割点 $k$。对角线初始化为 $i$，以便跟踪最优分割点。
更改 $k$ 的循环范围：更新循环范围为 $s(i,j-1)$ 到 $s(i+1,j)$，依据新加入的条件和 $s(i,j)$ 的值来选择分割点。
条件判断：用
if判断来选择分割点，而不是使用max/min。在更新 $f(i,j)$ 时，也同时更新 $s(i,j)$ 为当前的最优分割点 $k$。**更新 $f(i,j)$ 和 $s(i,j)$**：确保在每次更新 $f(i,j)$ 时，同时更新 $s(i,j)$。
这种优化能够利用四边形不等式加速动态规划计算过程，提高算法效率。
具体看别的大佬描述
四边形不等式优化讲解（详解）-CSDN博客
注: 由于石子合并求最大值以及最小值，所以对于最小值我们并不能进行平行四边形优化。