poj 2955 Brackets 区间DP

多做了几个区间DP后，还是有点感觉的，状态为什么要这样设计？状态转移方程为什么要这样写···

像这个题，紧紧抓住两个准则，就是正则括弧的两种形式（）[]左一段是正则的，右一段也是正则的，最优的结果要加起来

这就是转移方程要写成dp[i][j] = max(dp[i][j],dp[i][k] + dp[k+1][j]]的原因。。。k在i和j的中间

由于（[]）这种嵌套模式也是可以的，所以有if(a[i]与a[j]是匹配的) dp[i][j] = dp[i+1][j-1]+2```大概就是这样，细节自己注意一下就行

贴代码：

 1 #include <cstdio>
 2 #include <cstring>
 3 #define N 110
 4 #define max(a,b) a>b?a:b
 5 bool isMatch(char a,char b)
 6 {
 7     if(a=='(' && b == ')') return true;
 8     if(a == '[' && b == ']') return true;
 9     return false;
10 }
11 int main()
12 {
13     char a[N];
14     int dp[N][N];
15 //    freopen("in.cpp","r",stdin);
16     while(scanf("%s",a),strcmp(a,"end"))
17     {
18         int len = strlen(a);
19         memset(dp,0,sizeof(dp));
20         for(int k=1; k<len; ++k)
21         {
22             for(int i=0; i+k<len; ++i)
23             {
24                 int j=i+k;
25                 if( isMatch(a[i], a[j]) ) dp[i][j] = dp[i+1][j-1]+2;
26                 else dp[i][j] = max(dp[i+1][j], dp[i][j-1]);
27                 for(int t = i+1; t<j; ++t)
28                     dp[i][j] = max(dp[i][j],dp[i][t]+dp[t+1][j]);
29             }
30         }
31         printf("%d
",dp[0][len-1]);
32     }
33     return 0;
34 }

View Code