动态规划-区间DP
1. 区间DP的概念
区间DP，顾名思义就是在一个个的区间上进行DP。
2. 区间DP问题-石子合并
https://www.acwing.com/problem/content/284/
我们还是从动态规划的两个角度来阐述该问题。
1. 状态表示
本问题，我们可以用二维状态来表示。即，f[i,j]。那么，该二维状态所表示的集合为：所有将第i堆石子到第j堆石子合并成一堆石子的合并方式的集合。属性为：所有合并方式的总代价的最小值。
2. 状态计算
我们如何将f[i,j]划分为一个个的子集呢？我们发现，无论是哪一种合并方式，最后一步都是将两堆合并成一堆。因此，我们可以按照最后一步的合并情况来进行划分。
2.1 左边为1堆，右边为s-1堆所聚成的一堆。用区间表示：左边：[i,i],右边:[i+1,j]
2.2 左边为2堆聚成的一堆，右边为s-2堆所聚成的一堆。左边：[i,i+1],右边:[i+2,j]
...
2.s-1 左边为s-1堆聚成的一堆，右边为1堆。左边:[i,j-1],右边:[j,j]。
在上述子集中，s代表从i堆到j堆的石堆总数。即：s = j - i + 1;
我们可以将上述的子集划分，归纳成一般情况：
最后一步的合并情况：
实际上就是[i,k]和[k+1,j]两个区间进行合并。其中，k从i~j-1
根据上述的情况，我们可以发现：在最后一步的合并情况中，都是将两个石堆合并成一个石堆。因此，我们可以将每个合并情况中的合并步骤去掉(这样的话，不会影响最小值，因为最后一步的合并所花费的代价相等)，然后再加上这个最后一步合并所花费的代价即可。
因此，状态转移方程：
f[i][j] = min(f[i,k] + f[k+1,j] + s[j] - s[i-1])
其中，s[j] - s[i-1] 为最后一步合并所需要的代价(第i个石堆到第j个个石堆的质量之和)(通过前缀和算法来进行求解即可)。
k从i~j-1。
需要注意的就是：由于DP问题在计算某个状态时，该状态之前的状态都已经计算好了。因此，在区间DP中，我们在计算状态时，需要按照区间的长度来进行遍历。因为在状态计算的时候，都是将该区间的子区间进行合并。因此，我们需要按照区间长度从小到大来进行遍历。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 310;
int s[N];
int f[N][N];
int n;
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&s[i]);
}
//求解前缀和数组
for(int i=1;i<=n;i++){
s[i] += s[i-1];
}
//状态计算
//按照区间长度从小到大遍历
//先计算区间长度小的区间状态，再计算大的
//这样的话，就可以保证题目正确
//len=1的时候，只有一个石堆，不需要代价。
for(int len=2;len<=n;len++){
//遍历区间
//假设，i为左端点，右端点为x，则：len = x - i + 1 => x = len + i - 1;
for(int i=1; len + i - 1 <=n;i++){
int l = i;
int r = len + i - 1;
f[l][r] = 0x3f3f3f3f;
//遍历最后一步的划分情况
for(int k=l;k<r;k++){
f[l][r] = min(f[l][r],f[l][k] + f[k+1][r] + s[r] - s[l-1]);
}
}
}
printf("%d",f[1][n]);
return 0;
}
作者：gao79138
链接：https://www.acwing.com/
来源：本博客中的截图、代码模板及题目地址均来自于Acwing。其余内容均为作者原创。
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。