1.定义与性质
区间类动态规划是线性动态规划的扩展，它在分阶段地划分问题时，与阶段中元素出现的顺序和由前一阶段的哪些元素合并而来有很大的关系。
令状态 \(dp_{(i,j)}\) 表示将下标位置 \(i\) 到 \(j\) 的所有元素合并能获得的价值的最大值，那么 \(dp_{(i,j)}=max\{dp_{(i,k)}+dp_{(k+1,j)}+w\}\)，\(w\) 为将这两组元素合并起来的代价。
区间 \(dp\) 有如下特点：
-
1.合并：即将两个或多个部分进行整合，当然也可以反过来；
-
2.特征：能将问题分解为能两两合并的形式；
-
3.求解：对整个问题设最优值，枚举合并点，将问题分解为左右两个部分，最后合并两个部分的最优值得到原问题的最优值。
2.模板题
在一条链上有 \(n\) 个数 \(a_1,a_2,\dots,a_n\) 进行 \(n-1\) 次合并操作，每次操作将相邻的两堆合并成一堆，能获得新的一堆中的石子数量的和的得分。你需要最大化你的得分。
思路
令 \(dp_{(i,j)}\) 表示将区间 \([i,j]\) 内的所有石子合并到一起的最大得分。
写出状态转移方程：
\[dp_{(i,j)}=\max\{dp_{(i,k)}+dp_{(k+1,j)}+\sum_{t=i}^{j} a_t \}~(i\le k<j) \]然后我们用前缀和 \(sum\) 数组消掉求和公式，得：
\[dp_{(i,j)}=\max\{dp_{(i,k)}+dp_{(k+1,j)}+sum_j-sum_{i-1} \}~(i\le k<j) \]由于计算 \(dp_{(i,j)}\) 的值时需要知道所有 \(dp_{(i,k)}\) 和 \(dp_{(k+1,j)}\) 的值，而这两个中包含的元素的数量都小于 \(dp_{(i,k)}\)，所以我们以 \(len=j-i+1\) 作为 \(DP\) 的阶段。
首先从小到大枚举 \(len\)，然后枚举 \(i\) 的值，根据 \(len\) 和 \(i\) 用公式计算出 \(j\) 的值，然后枚举 \(k\)，时间复杂度为 \(O(n^3)\)
代码十分简单，这里不再摆出。
3.区间DP拓展知识之一—：如何处理带环的区间DP?
针对此问，一般有两种做法：
-
1.既然是带环的区间 \(DP\)，说明一定有 \(n\) 条连边，而题中又只能连 \(n-1\) 次，说明有一条边是用不上的，于是我们可以跑 \(n\) 遍区间 \(dp\)，枚举当每条边不被使用时的最优值。（时间复杂度 \(O(n^4)\)）
-
2.可以将这条链延长一倍，即将这条链复制下来接在其后面，最终结果为 \(dp_{(1,n)},dp_{(2,n+1)},dp_{(3,n+2)}...dp_{(n-1,2n-2)}\) 中的最优值，时间复杂度 \(O(n^3)\)。