区间dp

区间dp

区间dp属于线性dp的一种，以“区间长度”作为dp的“阶段”，用两个坐标(区间的左、右端点)描述每个维度。区间dp中，一个状态往往由若干个比它更小且包含于它的区间所代表的阶段转移而来，所以区间dp的决策往往就是划分dp的方法。

典型例题：石子合并

for(int i=1;i<=n;i++) f[i][i]=0;
for(int len=2;len<=n;len++){
	for(int i=1;i+len-1<=n;i++){
		int j=i+len-1;
		for(int k=i;k<j;k++){
			f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]+s[j]-s[i-1]);
            g[i][j]=max(g[i][j],g[i][k]+g[k+1][j]+s[j]-s[i-1]);
		}
	}
}