首页 > 代码库 > 给你一串括号，去掉最少的括号，使之合法化，输出合法化的长度。

给你一串括号，去掉最少的括号，使之合法化，输出合法化的长度。

2024-07-17 11:52:44   223人阅读

按照题目的四个条件去找就行了，小问题的解可以求出答题的解

dp[i][j]=max(dp[i][k]+dp[k+1][j],dp[i-1][j-1]+2)

 1 #include"iostream" 2 #include"cstring" 3 #include"cstdio" 4 using namespace std; 5 int main() 6 { 7     char str[150]; 8     while(scanf("%s",str)!=EOF) 9     {10         if(str[0]==‘e‘)11             break;12         int dp[150][150],i,j,k;13         int len=strlen(str);14         for(k=0;k<len;k++)  //增量放前   k=0用来初始化 15         {16             for(i=0;i+k<len;i++)17             {18                 int max=0;19                 if(i==i+k)20                 {21                     dp[i][i+k]=0;22                     continue;23                 }24                 if(str[i]==‘(‘&&str[i+k]==‘)‘)25                 {26                     if(i+1>i+k-1&&max<2)27                         max=2;28                     if(i+1<=i+k-1)29                     {30                         if(max<dp[i+1][i+k-1]+2)31                             max=dp[i+1][i+k-1]+2;32                     }33                 }34                 if(str[i]==‘[‘&&str[i+k]==‘]‘)35                 {36                     if(i+1>i+k-1&&max<2)37                         max=2;38                     if(i+1<=i+k-1)39                     {40                         if(max<dp[i+1][i+k-1]+2)41                             max=dp[i+1][i+k-1]+2;42                     }43                 }44                 for(j=1;j<=k;j++)45                 {46                     if(dp[i][i+j-1]+dp[i+j][i+k]>max)47                         max=dp[i][i+j-1]+dp[i+j][i+k];48                 } 49                 dp[i][i+k]=max;50             } 51         }52         printf("%d\n",dp[0][len-1]);53     }54     return 0;55 }

 


联系
我们