Description
Input
Output
Sample Input
([(]
Sample Output
()[()]
题意：给一串括号序列，按照合法括号的定义，添加若干括号，使得序列合法。
典型区间DP，设dp[i][j]为从i到j需要添加最少括号的数目。
dp[i][j] = max{ dp[i][k]+dp[k+1][j] } (i<=k<j)
如果s[i] == s[j] , dp[i][j] 还要和dp[i+1][j-1]比较。 枚举顺序按照区间长度枚举。
因为要求输出合法序列，就要记录在原序列在哪些位置进行了增加，设c[i][j]为从i到j的 增加括号的位置，如果不需要增加，那么c[i][j] 赋为-1，打印时只需递归打印即可。
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <math.h>
using namespace std;
typedef long long LL;
const int MAX=0x3f3f3f3f;
int n,c[105][105],dp[105][105];
char s[105];
void print(int i,int j) {
if( i>j ) return ;
if( i == j ) {
if(s[i] == '(' || s[i] == ')') printf("()");
else printf("[]");
return ;
}
if( c[i][j] > 0 ) { // i到j存在增加括号的地方，位置为c[i][j]
print(i,c[i][j]);
print(c[i][j]+1,j);
} else {
if( s[i] == '(' ) {
printf("(");
print(i+1,j-1);
printf(")");
} else {
printf("[");
print(i+1,j-1);
printf("]");
}
}
}
void DP() { //区间DP
for(int len=2;len<=n;len++)
for(int i=1;i<=n-len+1;i++) {
int j = i+len-1;
for(int k=i;k<j;k++) if( dp[i][j] > dp[i][k]+dp[k+1][j] ) {
dp[i][j] = dp[i][k] + dp[k+1][j];
c[i][j] = k; // 记录断开的位置
}
if( ( s[i] == '(' && s[j] == ')' || s[i] == '[' && s[j] == ']' ) && dp[i][j] > dp[i+1][j-1] ) {
dp[i][j] = dp[i+1][j-1];
c[i][j] = -1; //i到j不需要断开，因为dp[i+1][j-1]的值更小，上面枚举的k位置都比这个大，所以不再断开
}
}
}
int main()
{
scanf("%s",s+1);
n = strlen(s+1);
memset(c,-1,sizeof(c));
memset(dp,MAX,sizeof(c));
for(int i=1;i<=n;i++) dp[i][i] = 1, dp[i][i-1] = 0; //赋初值
DP();
print(1,n);
printf("\n");
return 0;
}
POJ 1141 Brackets Sequence （区间DP）,布布扣,bubuko.com
POJ 1141 Brackets Sequence （区间DP）
原文：http://blog.csdn.net/u013923947/article/details/38305979