POJ 2955-Brackets
区间 DP
题目描述：求一个字符串的最长括号匹配子串（非连续）
解题分析：状态转移方程全在题目里，定义了两种括号匹配的子串：
1若s是匹配的字符串，则（s）,[s]也是，那么状态转移方程是if(s[i] == '(' && s[j] ==')' || s[i] == '[' && s[j] ==']') dp[i][j] = max(dp[i][j],dp[i + 1][j - 1] + 2);。
2.若a是匹配的字符串，且b也是匹配的字符串,则ab是匹配的字符串。那么状态转移方程式：dp[i][j] = max(dp[i][j],dp[i][k] + dp[k+1][j])（i <= k < j）.
先写了一个记忆化搜索的：时间 170ms
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;
const int maxn = 100 + 10;
int dp[maxn][maxn];
char s[maxn];
int dfs(int u,int v)
{
if(dp[u][v] > -1) return dp[u][v];
if(u > v) return dp[u][v] = 0;
if(u == v) return dp[u][v] = 0;
int ans = 0;
if((s[u] == '(' && s[v] ==')' || s[u] == '[' && s[v] ==']' ) && v > u)
{
ans = max(ans,dfs(u + 1,v - 1) + 2);
}
for(int i = u; i < v; i++)
{
ans = max(ans,dfs(u,i) + dfs(i + 1,v));
}
return dp[u][v] = ans;
}
int main()
{
while(scanf("%s",s + 1) != EOF)
{
if(strcmp(s + 1,"end") == 0) break;
int n = strlen(s + 1);
memset(dp,-1,sizeof(dp));
cout << dfs(1,n) << endl;
}
return 0;
} 之后尝试些递推的，想了想，关于循环是顺序还是逆序这个得看状态转移方程，因为最终的答案是dp[1][n]，第一维的下标是由值大的下标推出来的，所以第一层循环是逆序，第二位下标由小的递推过来，所以第二层循环是顺序的。简而言之，就是看状态转移方程右边是如何递推出来左边的，从而确定循环的顺序。
代码如下：
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;
const int maxn = 100 + 10;
int dp[maxn][maxn];
char s[maxn];
int main()
{
while(scanf("%s",s + 1) != EOF)
{
if(strcmp(s + 1,"end") == 0) break;
int n = strlen(s + 1);
memset(dp,0,sizeof(dp));
for(int i = n; i >= 1; i--)
{
for(int j = i + 1; j <= n; j++)
{
for(int k = i; k < j; k++)
{
dp[i][j] = max(dp[i][j],dp[i][k] + dp[k+1][j]);
}
if(s[i] == '(' && s[j] ==')' || s[i] == '[' && s[j] ==']')
{
dp[i][j] = max(dp[i][j],dp[i + 1][j - 1] + 2);
}
}
}
cout << dp[1][n] <<endl;
}
return 0;
} 时间47ms，看来还是递推比较快。但无论怎样，记忆化搜索还是迭代的方法都不是绝对的，哪种能更好的A掉这个题，就选哪种。
如果要打印路径的话，代码如下：
void Print(int u,int v)
{
if(u > v) return;
if(dp[u + 1][v - 1] + 2 == dp[u][v] && (s[u] == '(' && s[v] ==')' || s[u] == '[' && s[v] ==']' ))
{
cout << s[u];
Print(u + 1,v - 1);
cout << s[v];
}
else
{
for(int k = u ; k < v; k++)
{
if(dp[u][v] == dp[u][k] + dp[k + 1][v])
{
Print(u,k);
Print(k + 1,v);
break;
}
}
}
}
联想公司福利 613人发布
