很好的区间DP题。
需要注意第一种情况不管是否匹配,都要枚举k来更新答案,比如:
“()()()”:dp[0][5]=dp[1][4]+2=4,枚举k,k=1时,dp[0][1]+dp[2][5]=6,最后取最大值6.
第一层d相当于“长度”的含义,第二层枚举i,j就可以用i+d表示,通过这种方式枚举区间左右端点。
1 #include<cstdio> 2 #include<cstdlib> 3 #include<cstring> 4 #include<cmath> 5 #include<algorithm> 6 #include<iostream> 7 using namespace std; 8 int dp[105][105]; 9 char s[105]; 10 11 bool match(int l,int r){ 12 if(s[l]=='('&&s[r]==')') return 1; 13 if(s[l]=='['&&s[r]==']') return 1; 14 return 0; 15 } 16 17 int main(){ 18 while(~scanf("%s",s)&&s[0]!='e'){ 19 int len=strlen(s); 20 memset(dp,0,sizeof(dp)); 21 for(int d=1;d<len;d++) 22 for(int i=0;i<len-d;i++){ 23 int j=i+d; 24 if(match(i,j))//括号成功匹配 25 dp[i][j]=dp[i+1][j-1]+2; 26 for(int k=i;k<j;k++)//不管匹配是否成功,都要进行这步操作,保证最优解 27 dp[i][j]=max(dp[i][j],dp[i][k]+dp[k+1][j]); 28 } 29 printf("%d\n",dp[0][len-1]); 30 } 31 return 0; 32 }