http://acm.pku.edu.cn/JudgeOnline/problem?id=1141
动态规划的一题 ，用三维数组保存中间状态；
 keeping studying......
//a数组动态记录串中不符合规则的符号个数
// R[i][j]数组动态记录from i dao j加上最少的符号个数后变成的串 
#include <iostream>
#include <string>
using namespace std;
int a[101][101];
char record[101];
string R[100][101];
int KHao(char p[], int n)
{
    int i, j, k, t;
    for(i = 0; i < n; i++)
        record[i] = 0;
      //初始化； 
    for(i = 1; i < n; i++){
          a[i][i - 1]  = 0;
          R[i][i - 1] = "";
          }
    for(i = 0; i < n; i++)a[i][i] = 1;
    for(t = 1; t < n; t++)
    {
        for(i = 0; i < n - t; i++)
        {    j = i + t;
            a[i][j] = 1000;
            if(p[i] == '('&&p[j] == ')'||p[i] == '['&&p[j] == ']')
            {
                if(a[i][j] > a[i + 1][j - 1])
                {
                    a[i][j] = a[i + 1][j - 1];
                    R[i][j] = p[i] + R[i + 1][j - 1] + p[j];
                }
            }
            if(p[i] == '('||p[i] == '[')
           {
                if(a[i][j] > a[i + 1][j] + 1)
                {
                    a[i][j] = a[i + 1][j] + 1;
                    if(p[i] == '(')
                       R[i][j] = "(" + R[i + 1][j] + ")";
                    if(p[i] == '[')
                    {
                       R[i][j] = "[" + R[i + 1][j] + "]";
                    }
                }
//                cout << i << " " << j << " " << R[i + 1][j] << endl;

           }
           if(p[j] == ')'||p[j] == ']')
           {  
               if(a[i][j] > a[i][j - 1] +1)
               {
                   a[i][j] = a[i][j - 1] + 1;
                   if(p[j] == ')')
                   {
                       R[i][j] = "(" + R[i][j - 1] + ")";
                   }
                   if(p[j] == ']')
                   {
                       R[i][j] = "[" + R[i][j - 1] + "]";
                   }       
               }
           }               
           for(k = i; k < j; k++)
           {
                if(a[i][j] > a[i][k] + a[k + 1][j])
                {
                    a[i][j] = a[i][k] + a[k + 1][j];
                    R[i][j] = R[i][k] + R[k + 1][j];
                }
           }
     //       cout << i << " " << j << " " << a[i][j] << endl;
        }
        
    }
    cout << R[0][n - 1] << endl;
    return n - a[0][n - 1];
    
}
int main()
{
    int p_l;
    int result;
    char p[101];
    int i, j, t;
    while(cin >> p)
    {
        if(p[0] == 'e')break;
        p_l = strlen(p);
        for(i = 0; i < p_l; i++)
        {
              //初始化； 
            if(p[i] == '('||p[i] == ')')
                R[i][i] = "()";
            if(p[i] == '['||p[i] == ']')
                R[i][i] = "[]";
        }
        KHao(p, p_l);
    }
    return 0;
}