poj 1141 括号匹配

根据“黑书”的思路，定义：

d[i][j]为输入序列从下标i到下标j最少需要加多少括号才能成为合法序列。0<=i<=j

c[i][j]为输入序列从下标i到下标j的断开位置，如果没有断开则为-1。

当i==j时，d[i][j]为1

当s[i]=='(' && s[j]==')' 或者 s[i]=='[' && s[j]==']'时，d[i][j]=d[i+1][j-1]

否则d[i][j]=min{d[i][k]+d[k+1][j]} i<=k

采用递推方式计算d[i][j]

输出结果时采用递归方式输出print(0, len-1)

输出函数定义为print(int i, int j)，表示输出从下标i到下标j的合法序列

当i>j时，直接返回，不需要输出

当i==j时，d[i][j]为1，至少要加一个括号，如果s[i]为'(' 或者')'，输出"()"，否则输出"[]"

当i>j时，如果c[i][j]>=0，说明从i到j断开了，则递归调用print(i, c[i][j]);和print(c[i][j]+1, j);

如果c[i][j]<0，说明没有断开，如果s[i]=='(' 则输出'('、 print(i+1, j-1); 和")"

否则输出"[" print(i+1, j-1);和"]"

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       using namespace std; int dp[100][100]; int c[100][100]={-1}; int len; char s[1000]; void cal(){ for(int i=0;i
      
       j)return ; if(i==j){ if(s[i]=='('||s[j]==')') cout<<"()"; else cout<<"[]"; } if(i
       
        =0){ print(i,c[i][j]); print(c[i][j]+1,j); } else { if(s[i]=='('){ cout<<"("; print(i+1,j-1); cout<<")"; } else if(s[i]=='['){ cout<<"["; print(i+1,j-1); cout<<"]"; } } } } int main(){ cin>>s; len=strlen(s); cal(); print(0,len-1); puts(""); }