区间 dp

例：石子合并

集合表示，把 dp[i][j] 作为 i 堆到 j 堆的区间的最小代价 (min)

然后是集合划分，如何才能把它划分成划分？(或者覆盖但 max 不管)，而且还把问题缩小了？由于此题只能左右相邻堆合并，所以考虑根据左 1、2、3、…、k-1 的方式分

那么 dp[i][j]=min(dp[i][k]+dp[k+1][j]) + sum(i,j)

这个公式表达的是，到 ij 这一步合成，一定是最后是两堆合进来的，那就需要合成这两堆之后，再来合一下这个

这里要计算一个区间内的和，为了快速用前缀和最快。

for(int len = 2; len <= n; ++len) {  // len 1 集合划分不了了
	for(int i = 1; i+len-1 <= n; ++i) {
		int l = i, r = i+len-1;
		dp[l][r] = 1e8;  // 初始高值
		for(int k = l; k < r; ++k) {  // 这里是闭区间
			dp[l][r] = min(dp[l][r], dp[l][k]+dp[k+1][r]+s[r]-s[l-1]);
		}
	}
}
return dp[1][n];

类似的，计算当前状态需要子状态，这要求子状态已经提前算过了，类似于 01 背包 倒过来循环防覆盖，这里计算 i---k---j 需要的子区间起点终点不确定，所以经典 ij 套循环，会让 kj 并未计算过

但注意到 ik，kj 的区间长度一定小于 ij，所以如果按照区间长度枚举，就能确保计算 ij 时，子集合一定都算过了

也就是先循环区间长度，再循环左端点，再计算右端点