所谓区间dp，顾名思义就是在一段区间上的动态规划。它既要满足dp问题的最优子结构和无后效性外，还应该符合在区间上操作的特点。我的理解是往往会对区间进行合并操作。抑或是单个元素（可看成一个小区间）跨区间进行操作。例如括号匹配问题，石子合并问题（通过多次的相邻合并，最后实质上会产生跨区间的合并，如果你把其中的石子看作参考系的话就很容易感觉出来），还有在整数中插入运算符号的问题（利用运算符的优先级以及交换律可看出）
这样以来，如果我们要得知一个大区间的情况，由于它必定是由从多个长度不一的小区间转移而来（转移情况未知），我们可以通过求得多个小区间的情况，从而合并信息，得到大区间。
对于一个长度为n的区间，确定它的子区间需要首尾两个指针，显然子区间数量级为n2，那区间dp的复杂度也就为n2
操作的模板
1 for (int len = 1; len < n; len++) { //操作区间的长度2 for (int i = 0, j = len; j <= n; i++, j++) { //始末3 //检查是否匹配（非必须）4 for (int s = i; s < j; s++) {5 //update6 }7 }8 }
1 #include2 #define min(x, y) (x > y ? y : x) 3 #define INF 0x3f3f3f3f 4 using namespace std; 5 6 const int maxn = 210; 7 int dp[maxn][maxn]; 8 int sum[maxn]; 9 int a[maxn];10 11 int main(int argc, const char * argv[]) {12 13 int n;14 while (~scanf("%d", &n)) {15 for (int i = 1; i <= n; i++) {16 scanf("%d", &a[i]);17 sum[i] = sum[i - 1] + a[i];18 }19 for (int len = 1; len < n; len++) { //操作区间的长度20 for (int i = 1, j = len + 1; j <= n; i++, j++) { //始末21 //检查是否匹配（非必须）22 dp[i][j] = INF;23 for (int s = i; s < j; s++) {24 dp[i][j] = min(dp[i][j], dp[i][s] + dp[s + 1][j] + sum[j] - sum[i - 1]);25 }26 }27 }28 printf("%d\n", dp[1][n]);29 }30 return 0;31 }
1 #include2 #include 3 #include 4 using namespace std; 5 6 const int maxn = 105; 7 char str[maxn]; 8 int dp[maxn][maxn]; 9 10 bool ck(int i, int j) {11 if ((str[i] == '(' && str[j] == ')') || (str[i] == '[' && str[j] == ']')) {12 return true;13 } else {14 return false;15 }16 }17 18 int main(int argc, const char * argv[]) {19 while (~scanf("%s", str)) {20 if (str[0] == 'e') break;21 22 int len;23 len = strlen(str);24 memset(dp, 0, sizeof(dp));25 for (int l = 1; l < len; l++) { //len = j - i 为当前区间长度26 for (int i = 0, j = l; j < len; i++, j++) { // i++, j++27 if (ck(i, j)) { // 匹配28 dp[i][j] = dp[i + 1][j - 1] + 2;29 }30 // 讨论区间合并情况，求最大值31 for (int pos = i; pos < j; pos++) {32 dp[i][j] = max(dp[i][j], dp[i][pos] + dp[pos + 1][j]);33 }34 }35 }36 printf("%d\n", dp[0][len - 1]);37 38 }39 return 0;40 }
四边形不等式优化优化以后再学