看还没有人发记搜的题解，赶紧来水发一篇

我们定义dp[i][j]为区间i~j内最少添加几个括号才能把这个串变成正规括号序列。

考虑四种情况

1. i>j不存在这种子串，返回0

2. i==j子串长度为1无论是"[","]","(",")"都是要消耗1的，返回1

3. s=(s')或s=[s']那么返回的是DP(i+1,j-1)

4. 其他情况，枚举断点，详见代码

至于输出嘛.....不会，看紫书的，输出代码的解释看看楼上吧，这里就不详细解释了

代码:

#include
    
     using namespace std;const int INF=0x3f3f3f3f;int T,n;string s;int dp[110][110];//记忆inline int DP(int l,int r)//记搜{    if(l==r)return dp[l][r]=1;//②    if(l>r)return dp[l][r]=0;//①    if(dp[l][r]!=INF)return dp[l][r];//记忆化    if(s[l-1]=='('&&s[r-1]==')'||s[l-1]=='['&&s[r-1]==']')dp[l][r]=min(dp[l][r],DP(l+1,r-1));//③    for(int i=l;i
     
      r)return;    if(l==r)    {        if(s[l-1]=='('||s[l-1]==')')            cout<<"()";        if(s[l-1]=='['||s[l-1]==']')            cout<<"[]";        return;    }    if(dp[l][r]==dp[l+1][r-1]&&((s[l-1]=='('&&s[r-1]==')')||(s[l-1]=='['&&s[r-1]==']')))    {        cout<