区间DP主要是把一个大区间拆分成几个小区间,先求小区间的最优值,然后合并起来求大区间的最优值。 区间DP最关键的就是满足最优子结构以及无后效性!!! //一般区间DP实现代码 memset(dp, 0x3f, sizeof(dp)); for (int i = 1; i <= n; i++) //区间长度为1的初始化 dp[i][i] = 0; for (int len = 2; len <= n; len++) //枚举区间长度 { for (int i = 1, j = len; j <= n; i++, j++) //区间[i,j] { //DP方程实现 } } 我...