首页 > 代码库 > 给你一串括号,去掉最少的括号,使之合法化,输出合法化的长度。
给你一串括号,去掉最少的括号,使之合法化,输出合法化的长度。
按照题目的四个条件去找就行了,小问题的解可以求出答题的解
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 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。