大家好，又见面了，我是全栈君，今天给大家准备了Idea注册码。
取血怒。first blood，第一区间DP，这样第一次没有以某种方式在不知不觉中下降~~~
题目尽管是鸟语。但还是非常赤裸裸的告诉我们要求最大的括号匹配数。DP走起~
dp[i][j]表示区间[i,j]的最大匹配数。那么最重要的状态转移方程就是：
dp[i][j]=max(dp[i][k]+dp[k+1][j])
对啦，要先初始化边界啊。两步走~：
memset(dp,0,sizeof dp);
if str[i]==str[i+1] 则:dp[i][i+1]=2 请看—->> 该字符串 ( [ ] [ ] [ ) 非常好懂有木有
万恶的贴代码：
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
int dp[110][110];
char s[110];
bool check(int i,int j)//推断是不是匹配的
{
if(s[i]=='['&&s[j]==']') return true;
if(s[i]=='('&&s[j]==')') return true;
return false;
}
int main()
{
while(scanf("%s",s)!=EOF){
if(strcmp(s,"end")==0) break;
int l=strlen(s);
memset(dp,0,sizeof dp);
for(int i=0;i<l;i++){ //初始化
if(check(i,i+1)){
dp[i][i+1]=2;
}
}
for(int p=3;p<=l;p++){ //枚举区间长度
for(int i=0;i<=l-p;i++){ //枚举区间起点
int j=i+p-1;
if(check(i,j)){
dp[i][j]=dp[i+1][j-1]+2;
}
for(int k=i;k<j;k++){ //将区间分成两段
dp[i][j]=max(dp[i][j],dp[i][k]+dp[k][j]);
}
}
}
cout<<dp[0][l-1]<<endl;
}
return 0;
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/116728.html原文链接：https://javaforall.net
