虽然取最值的状态划分可以有重叠,但是我还是希望搞清楚为什么必须要重叠

一句话就是,重叠了才能保证取整个区域的最值,否则有时只会取状态划分区域中一部分的最值

int &t = f[i][j];
if(q[i] == q[j]) t = f[i+1][j-1];
else{
	for(int k = i; k <= j-1; k ++) t = min(t, f[i][k] + f[k+1][j]);
}

我们把第i个珠子和第j个珠子不相等的状态划分记为s1,把另一部分记作s2,如果我们加上else的话,那么在满足区域s1的条件的时候,t=min(s1),而不是min(s1,s2)忽略掉了另一部分