区间DP

区间DP

1.一般以区间为动态规划的阶段

2.石子合并

在一个圆形操场的四周摆放 NN 堆石子,现要将石子有次序地合并成一堆.规定每次只能选相邻的2堆合并成新的一堆，并将新的一堆的石子数，记为该次合并的得分。

试设计出一个算法,计算出将 N 堆石子合并成 1 堆的 最小得分 和 最大得分。

最小和最大的区别只有使用的是max还是min。下面以最大的情况为例
便于思考我们假设不是环形的：
很容易想到，定义dp[i][j]是合并第i到第j堆的最佳解。
状态转移方程为
dp[i][j] = max(dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1);
可以理解为把i~j这个区间分成两段，枚举每一种可能，求最大值。

最后的答案为dp[1][n]。

至于环形问题，可以考虑使用取模的方式来处理，但是我认为把长度扩大两倍的方法会更加直白，并且一些问题中可能会出现减法。取模会更加麻烦。

3.代码模板

之前喜欢从上而下的用记忆化搜索写，后来发现一些题目从上往下不好思考。
看别人的代码也是从下往上的。
然后就现在就写个板子(DP板子都比较短hhh)

for(int l = 1;l <= n;l++){//枚举区间长度
	for(int i = 1;i <= n-l;i++){//枚举起点
		int j = l+i;//生成终点
		for(int k = i;i <= j-1;j++){
		/*写状态转移方程*/
		}
	}
}