求一个括号的最大匹配数，这个题可以和比较着看。

注意题目背景一样，但是所求不一样。

回到这道题上来，设d(i, j)表示子序列S_i ~ S_j的字符串中最大匹配数，如果S_i 与 S_j能配对，d(i, j) = d(i+1, j-1)

然后要枚举中间点k，d(i, j) = max{ d(i, k) + d(k+1, j) }

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 using namespace std; 6  7 const int maxn = 100 + 10; 8  9 int n;10 char s[maxn];11 int d[maxn][maxn];12 13 bool inline match(char c1, char c2)14 {15     if(c1 == '[' && c2 == ']') return true;16     if(c1 == '(' && c2 == ')') return true;17     return false;18 }19 20 int main()21 {22     while(scanf("%s", s) == 1 && s[0] != 'e')23     {24         n = strlen(s);25         for(int i = 0; i + 1 < n; i++)26         {27             if(match(s[i], s[i+1])) d[i][i+1] = 2;28             else d[i][i+1] = 0;29         }30 31         for(int l = 3; l <= n; l++)32         {33             for(int i = 0; i + l - 1 < n; i++)34             {35                 int j = i + l - 1;36                 d[i][j] = 0;37                 if(match(s[i], s[j])) d[i][j] = d[i+1][j-1] + 2;38                 for(int k = i; k < j; k++)39                     d[i][j] = max(d[i][j], d[i][k] + d[k+1][j]);40             }41         }42 43         printf("%d\n", d[0][n-1]);44     }45 46     return 0;47 }