使用的dp,主要的难度来自于对串的储存，很经典的dp,可以参看黑素115夜

 

感谢stl，还是很方便的东西

 

 

#include <iostream>
#include <string>
using namespace std;
string ans[110][110];
string s;
int d[110][110]={0};
bool index[110][110]={0};
int bb(int f,int e)
{
 if(index[f][e])
  return d[f][e];

 else if(f&gt;e) {return 0;}
 else if (f==e)
 {
  
   if (s[f] == '(') ans[f][e] = "()";
            if (s[f] == ')') ans[f][e] = "()";
            if (s[f] == '[') ans[f][e] = "[]";
            if (s[f] == ']') ans[f][e] = "[]";
   return 1;

 }

 else
 {
  int aans=0xfffffff;
  if(s[f]=='('&&s[e]==')')
  {
   if(bb(f+1,e-1)<aans)
   {
    aans=bb(f+1,e-1);
    ans[f][e]='('+ans[f+1][e-1]+')';
   }
  }
  else if(s[f]=='['&&s[e]==']')
  {
   if(bb(f+1,f-1)&lt;aans)
   {
    aans=bb(f+1,e-1);
    ans[f][e]='['+ans[f+1][e-1]+']';
   }
  }
/*  else if(s[f]=='[')
  {
   if(bb(f+1,e)+1&lt;aans)
   {
    aans=bb(f+1,e)+1;
    ans[f][e]=ans[f+1][e]+']';
   }
  }
  else if(s[f]=='(')
  {
   if(bb(f+1,e)+1&lt;aans)
   {
    aans=bb(f+1,e)+1;
    ans[f][e]=ans[f+1][e]+')';
   }
  }
  else if(s[e]==')')
  {
   if(bb(f,e-1)+1&lt;aans)
   {
    aans=bb(f,e-1)+1;
    ans[f][e]='('+ans[f][e-1];
   }
  }
  else if(s[e]==']')
  {
   if(bb(f,e-1)+1&lt;aans)
   {
    aans=bb(f,e-1)+1;
    ans[f][e]='['+ans[f][e-1];
   }
  }
  */
  for(int i=f;i&lt;e;i++)
  if(aans>bb(f,i)+bb(i+1,e))
  {
   aans=bb(f,i)+bb(i+1,e);
   ans[f][e]=ans[f][i]+ans[i+1][e];
  }
 d[f][e]=aans;
 index[f][e]=true;
 return aans;

 }
}
int main()
{
 cin &gt;&gt;s;
 if(s.empty())
 {
  cout&lt;&lt;endl;
  return 0;
 }
 int b;
 b=bb(0,s.size()-1);
 cout&lt;&lt;ans[0][s.size()-1]&lt;&lt;endl;
 return 0;

}