区间 DP
区间 DP 是对一个区间的合并的代价的最优值。通常区间 \(DP\) 符合以下几个特点：
- 合并：即将两个或多个部分进行整合，当然也可以反过；
- 特征：能将问题分解为能两两合并的形式；
- 求解：对整个问题设最优值，枚举合并点，将问题分解为左右两个部分，最后合并两个部分的最优值得到原问题的最优值。
一般设 \(f[i][j]\) 为把 \(i\) 到 \(j\) 的元素合并起来所需要的代价，状态转移方程是
$$f[i][j] = \max(f[i][k],f[k+1][j])$$
这里找一道很经典的题目来看一下：
题目
链接 ： 传送门
石子合并
题目描述
在一个圆形操场的四周摆放 \(N\) 堆石子,现要将石子有次序地合并成一堆.规定每次只能选相邻的2堆合并成新的一堆，并将新的一堆的石子数，记为该次合并的得分。
试设计出一个算法,计算出将 \(N\) 堆石子合并成 \(1\) 堆的最小得分和最大得分。
输入格式
数据的第 \(1\) 行是正整数 \(N\)，表示有 \(N\) 堆石子。
第 \(2\) 行有 \(N\) 个整数，第 \(i\) 个整数 \(a_i\) 表示第 \(i\) 堆石子的个数。
输出格式
输出共 \(2\) 行，第 \(1\) 行为最小得分，第 \(2\) 行为最大得分。
数据范围
\(1≤N≤100，0≤ai≤200\leq a_i\leq 200≤ai≤20。\)
思路
这道题的状态转移方程为 \(f[i][j] = \max(f[i][j],f[i][k]+f[k][j] + \sum\limits_{t=1}^j a_t)\)
这一题是很经典的区间 DP 题，但是这里有一点不一样：不是一个区间了，而是一个环了，这样就会导致终点与起始点重合（同一个点），所以我们可以枚举断开点，再对每个进行 \(dp\)，一共有 \(n\) 个断开点，所以时间复杂度是 \(\mathcal{O}(n^5)\) 会超时，不可取。
这时候我们想到想要把环变成一个链，还可以把这个我们将这条链延长两倍；变成 \(2 \times n\) 堆，其中第 \(i\) 堆与第 \(n \times i\) 堆相同，然后再进行动态规划。
最后再找 \(f[i][i+n-1]\) 中的最大值（最小值），就是最大值（最小值）的答案。时间复杂度为 \(\mathcal{O}(n^4)\)，还是有点慢，可以用前缀和来优化，最终时间复杂度为 \(\mathcal{O}(n^3)\) ，最终的状态转移方程为：
\[f[i][j] = \max(f[i][j],f[i][k]+f[k][j] + sum[j]-sum[i-1]) \]AC 代码
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
int dp[400][400] = {0},dp2[400][400] = {0},a[200],sum[300] = {0};
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
a[n+i] = a[i];
}
for(int i=1;i<=n+n;i++)
sum[i] = sum[i-1] + a[i];
for(int i=1;i<=300;i++)
for(int j=1;j<=300;j++)
dp2[i][j] = 9999999; \\求 min 时必须初始化为较大值
for(int i=0;i<=2*n;i++) dp2[i][i]=0;
//核心代码
for (int len = 1; len <= n; len++)
for (int i = 1; i <= 2 * n - 1; i++) {
int j = len + i - 1;
for (int k = i; k < j && k <= 2 * n - 1; k++){
dp[i][j] = max(dp[i][j], dp[i][k] + dp[k+1][j] + sum[j] - sum[i-1]);
dp2[i][j] = min(dp2[i][j],dp2[i][k] + dp2[k+1][j] + sum[j] - sum[i-1]);
}
}
int maxn = -1;
int minn=9999999;
for(int i=1;i<=n;i++){
maxn = max(maxn,dp[i][n+i-1]);
minn = min(minn,dp2[i][n+i-1]);
}
printf("%d\n%d\n",minn,maxn);
return 0;
}