对于这道题目WA的我想说：老子裤子都脱了，你就给我看这个？！ 开始做的时候，随意看了一下案例，就是左右括号可以匹配，题目给的字符串可能不是完全都有匹配的 比如 (([]),这里就是差了一个),应该补全了输出 (([]))
思路还是比较简单的，区间dp,dp[i][j]表示 区间 i 到j之间的匹配数，在这里有特殊情况的 就是 这个区间是一个闭合区间，要判断区间两端的 字符是否可以刚好匹配,若可以匹配 状态转移就多了一个 dp[i][j] = max(dp[i][k]+dp[k+1][j],dp[i+1][j-1]+1),若不能匹配就是dp[i][j] = max(dp[i][j],dp[i][k]+dp[k+1][j]);
若是两端可以匹配的，而且两端匹配了导致的dp值最大那么就标记一下，mark[i][j] = -1,否则 就mark[i][j] = k，这样把所有区间都dp一遍，回头再用DFS寻找，若是两端匹配导致值最大的 那么就直接输出这个字符标记一下，继续往更小的区间去搜索，否则 就分开两个区间搜索 [i,k] [k+1,j],
由于值区间dp，所以被标记的就是本来就有匹配的，那么直接输出这个字符，否则就输出一对匹配的字符
思路是对的，但是一直WA啊，改 啊改啊，但是还是WA，觉得思路非常清晰也很正确啊，经典的区间DP题目啊，后来看看大牛的博客，发现思路都是一样的啊，没什么区别，搞了两个半小时，实在受不了了，后来发现别人输入用的是getline，我抱着尝试的心态，试了改一下，居然过了，无语， 去看看getline是什么玩意了
#include<iostream>
#include<cstdio>
#include<list>
#include<algorithm>
#include<cstring>
#include<string>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#include<cmath>
#include<memory.h>
#include<set>
#define ll long long
#define eps 1e-7
#define inf 0xfffffff
//const ll INF = 1ll<<61;
using namespace std;
//vector<pair<int,int> > G;
//typedef pair<int,int > P;
//vector<pair<int,int> > ::iterator iter;
//
//map<ll,int >mp;
//map<ll,int >::iterator p;
//#define IN freopen("c:\\Users\\linzuojun\\desktop\\input.txt", "r", stdin)
//#define OUT freopen("c:\\Users\\linzuojun\\desktop\\output.txt", "w", stdout)
//
//void TestArray()
//{
// char chs[] = {‘a‘, ‘d‘, ‘c‘, ‘e‘, ‘b‘};
// int count = sizeof(chs)/sizeof(char);
//
// next_permutation(chs+0, chs + count);
//
// printf("TestArray:\n");
// for(int i = 0; i < count; i++) {
// printf("%c\t", chs[i]);
// }
//
// printf("\n");
//}
//
//void TestVector()
//{
// char chs[] = {‘a‘, ‘d‘, ‘c‘, ‘e‘, ‘b‘};
// int count = sizeof(chs)/sizeof(char);
// vector<char> vChs(chs, chs + count);
//
// next_permutation(vChs.begin(), vChs.end());
//
// printf("TestVector:\n");
// vector<char>::iterator itr;
// for(itr = vChs.begin(); itr != vChs.end(); itr++) {
// printf("%c\t", *itr);
// }
// printf("\n");
//}
//
//int main(int argc, char *argv[])
//{
// TestArray();
// printf("\n");
// TestVector();
//
// system("PAUSE");
//
// return EXIT_SUCCESS;
//}
int dp[100 + 5][100 + 5];
int mark[100 + 5][100 + 5];
int pos[100 + 5];
void clear() {
memset(dp,0,sizeof(dp));
for(int i=0;i<105;i++)
for(int j=0;j<105;j++)
mark[i][j] = -2;
memset(pos,0,sizeof(pos));
}
void dfs(int i,int j) {//倒回去搜索过程超级简单，就是DP过程嘛
if(mark[i][j] == -1) {//闭区间两头可以匹配
pos[i] = 1;
pos[j] = 1;
dfs(i+1,j-1);
}
else if(mark[i][j] >= 0) {
dfs(i,mark[i][j]);
dfs(mark[i][j]+1,j);
}
else return ;
}
int main() {
string s;
while(getline(cin,s)) {
clear();
int i = 0;
int j = 0;
int k = 0;
while(k < s.length()) {
if(i == j) {
i++;
j++;
if(j == s.length()) {
i = 0;
k++;
j = k;
}
continue;
}
if((s[i] == ‘[‘ && s[j] == ‘]‘) || (s[i] == ‘(‘ && s[j] == ‘)‘)) {//闭区间两头可以匹配
for(int l=i;l<j;l++) {
if(dp[i][j] < dp[i][l] + dp[l+1][j]) {
mark[i][j] = l;
dp[i][j] = dp[i][l] + dp[l+1][j];
}
}
if(dp[i][j] < dp[i+1][j-1] + 1) {
mark[i][j] = -1;
dp[i][j] = dp[i+1][j-1] + 1;
}
}
else {
for(int l=i;l<j;l++) {
if(dp[i][j] < dp[i][l] + dp[l+1][j]) {
mark[i][j] = l;
dp[i][j] = dp[i][l] + dp[l+1][j];
}
}
}
i++;
j++;
if(j == s.length()) {
i = 0;
k++;
j = k;
}
}
dfs(0,s.length() - 1);
for(int i=0;i<s.length();i++) {
if(pos[i] == 1)
cout<<s[i];
else {
if(s[i] == ‘(‘ || s[i]==‘)‘)
cout<<"()";
else
cout<<"[]";
}
}
puts("");
}
return EXIT_SUCCESS;
}
POJ1141 ZOJ1463 Brackets Sequence 经典动态规划 区间DP
原文：http://blog.csdn.net/yitiaodacaidog/article/details/19704085