这篇文章上次修改于 339 天前，可能其部分内容已经发生变化，如有疑问可询问作者。
区间$DP$将区间作为状态进行$DP$。
P1880是很典型的区间$DP$。设$dp_{i,j}$为已经将$i,j$之间的合并后的结果。
接下来考虑如何枚举，$DP$ 枚举的关键是三大点：
1、不会出现后效性。
2、考虑第某个情况时，它所需要的子情况已经求解。
3、不会违反题意。
很显然$dp_{i,j}$明显是由2个更小的区间合并，所以可以在第一层循环中枚举区间大小$L(2<=L<=N)$第二层则枚举区间起点。那这个区间就已经确定了，再在区间内枚举分割点。即可AC。（记得断环为链）