区间DP poj 2955

求最多有几个括号可以匹配
 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<algorithm>
 4 
 5 using namespace std;
 6 #define MAXN 110
 7 
 8 int dp[MAXN][MAXN];
 9 char z[MAXN];
10 
11 int main()
12 {
13     while(scanf("%s",z)!=EOF)
14     {
15         if(strcmp(z,"end")==0)
16             break;
17 
18         int len=strlen(z);
19 
20         memset(dp,0,sizeof(dp));
21         int l,i,j,k;
22 
23         for(l=2;l<=len;l++)  //列举长度
24         {
25             for(i=0;i<=len-l;i++)
26             {
27                 j=i+l-1;
28                 if((z[i]=='('&&z[j]==')')||(z[i]=='['&&z[j]==']'))
29                     dp[i][j]=dp[i+1][j-1]+2;
30 
31                 for(k=i;k<=j;k++) //取最大
32                     dp[i][j]=max(dp[i][j],dp[i][k]+dp[k+1][j]);
33             }
34         }
35         printf("%d
",dp[0][len-1]);
36     }
37 
38 
39     return 0;
40 }