題目：

給出一個有括號的字符串，問這個字符串中能匹配的最長的子串的長度。

思路：

區間DP，首先枚舉區間長度，然后在每一個長度中通過枚舉這個區間的分割點來更新這個區間的最優解。還是做的少。

代碼:

//#include <bits/stdc++.h> #include <cstdio> #include <cstring> #include <iostream> #define MAX 1000000000 #define FRE() freopen("in.txt","r",stdin)using namespace std; const int maxn = 105; char str[maxn]; int dp[maxn][maxn];int main() {//FRE();while(gets(str)){if(strcmp(str,"end")==0) { break; }if(strcmp(str,"")==0) {printf("0\n"); break;}int length = strlen(str);for(int i=0; i<length; i++){for(int j=0; j<length; j++){ dp[i][j] = 0; }}//printf("length: %d\n",length);for(int len=1; len<length; len++)//枚舉區間的長度 {for(int i=0; i+len<length; i++){int j = i+len;if((str[i]=='(' && str[j]==')') || (str[i]=='['&&str[j]==']')){dp[i][j] = max(dp[i+1][j-1]+2,dp[i][j]);//當前這個區間是由哪個區間得來的 }for(int k=i; k<=j; k++)//更新這個區間的最優解 {dp[i][j] = max(dp[i][j],dp[i][k]+dp[k+1][j]);}}} // printf("%d\n",dp[1][2]); // printf("%d\n",dp[3][4]); // printf("%d\n",dp[1][4]); // printf("%d\n",dp[1][5]);printf("%d\n",dp[0][length-1]);}return 0; }

?

轉載于:https://www.cnblogs.com/sykline/p/10497140.html

總結

以上是生活随笔為你收集整理的POJ - 2955 Brackets （区间DP）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。