http://poj.org/problem?id=1141
Let us define a regular brackets sequence in the following way:
1. Empty sequence is a regular sequence.
2. If S is a regular sequence, then (S) and [S] are both regular sequences.
3. If A and B are regular sequences, then AB is a regular sequence.
For example, all of the following sequences of characters are regular brackets sequences:
(), [], (()), ([]), ()[], ()[()]
And all of the following character sequences are not:
(, [, ), )(, ([)], ([(]
Some sequence of characters '(', ')', '[', and ']' is given. You are to find the shortest possible regular brackets sequence, that contains the given character sequence as a subsequence. Here, a string a1 a2 ... an is called a subsequence of the string b1 b2 ... bm, if there exist such indices 1 = i1 < i2 < ... < in = m, that aj = bij for all 1 = j = n.
1. Empty sequence is a regular sequence.
2. If S is a regular sequence, then (S) and [S] are both regular sequences.
3. If A and B are regular sequences, then AB is a regular sequence.
For example, all of the following sequences of characters are regular brackets sequences:
(), [], (()), ([]), ()[], ()[()]
And all of the following character sequences are not:
(, [, ), )(, ([)], ([(]
Some sequence of characters '(', ')', '[', and ']' is given. You are to find the shortest possible regular brackets sequence, that contains the given character sequence as a subsequence. Here, a string a1 a2 ... an is called a subsequence of the string b1 b2 ... bm, if there exist such indices 1 = i1 < i2 < ... < in = m, that aj = bij for all 1 = j = n.
Input
The input file contains at most 100 brackets (characters '(', ')', '[' and ']') that are situated on a single line without any other characters among them.
Output
Write to the output file a single line that contains some regular brackets sequence that has the minimal possible length and contains the given sequence as a subsequence.
Sample Input
([(]
Sample Output
()[()]
思路和POJ 2955是类似的。我们用DP[i][j]表示把子串s[i, j]补完成合法序列所需要的最少的字符数。我们有递推公式：
- DP[i][j] = D[i + 1][j]，如果s[i]在s[i + 1, j]中没有括号与之match
- DP[i][j] = max(dp[i + 1][k - 1] + dp[k + 1][j])，如果s[i]和s[k]match
但是这个公式只能算出最少需要补完多少个字符来使之合法。我们还需要记录打印结果的路径(只打印满足条件的一个即可），我们用path[i][j]来记录s[i,j]的分割点，如果s[i]没有match，path[i][j] = -1；如果s[i]和s[k]match且其使得需要补完的char数最少，path[i][j] = k。我们打印的时候根据path自上而下递归地打印即可，详细可以参见代码中的print方法。时间复杂度空间复杂度均为O(n^2)
int dp[MAX][MAX], path[MAX][MAX];
char s[MAX];
void print(int i, int j)
{
if(i > j)return;
if(i == j)
{
if(s[i] == '(' || s[i] == ')')printf("()");
else printf("[]");
return;
}
if(path[i][j] == -1)
{
print(i, i);
print(i + 1, j);
}
else
{
int k = path[i][j];
printf("%c", s[i]);
print(i + 1, k - 1);
if(s[i] == '(')printf(")");
else printf("]");
print(k + 1, j);
}
}
int main()
{
while(gets(s))
{
int len = strlen(s);
if(len == 0)
{
printf("\n");
continue;
}
memset(dp, 0, sizeof(dp[0][0] * MAX * MAX));
memset(path, 0, sizeof(path[0][0] * MAX * MAX));
for(int i = 0; i < len; ++i)dp[i][i] = 1;
for(int j = 0; j < len; ++j)
{
for(int i = j - 1; i >= 0; --i)
{
//assume s[i] doesn't match
dp[i][j] = dp[i + 1][j] + 1;
path[i][j] = -1;
for(int k = i + 1; k <= j; ++k)
{
if(s[i] == '(' && s[k] == ')' || s[i] == '[' && s[k] == ']')
{
int cost = dp[i + 1][k - 1] + dp[k + 1][j];
if(cost < dp[i][j])
{
dp[i][j] = cost;
path[i][j] = k;//s[k] matches s[i]
}
}
}
}
}
print(0, len - 1);
printf("\n");
}
简单区间dp，对于一段区间，分三种情况讨论：
1、这个区间被分成多块。（regular sequence算是一块）
2、整个是一块，且两边分别保留一个字符。
3、整个是一块，且只保留一边的一个字符。
1、这个区间被分成多块。（regular sequence算是一块）
2、整个是一块，且两边分别保留一个字符。
3、整个是一块，且只保留一边的一个字符。
题意：添加最少的符号，使得它是完美的。
思路：用dp[i][j]表示修i到j需要的最少符号数量
解题思路：与POJ 2955 Brackets这题一样，是一个区间DP的题。思想很类似，但有些许差异。设dp[l][r]表示区间[l,r]内至少需要增加的括号数，则状态转移如下：
1、l==r时，dp[l][r]显然为1；
2、l与r匹配时，dp[l][r] = min(dp[l][r], dp[l+1][r-1])；
3、l与r不匹配时，可将区间[l,r]分成两个区间[l,mid]和[mid+1,r]，其中l<=mid<r。
注意：不管上述2是否满足，都要去尝试上述3，否则就会出现"[][]"转移到"]["的情况，这样就只能够添加两个括号了。还有一个注意点就是，当l>r时，要更新dp[l][r]=0，否则在输出结果时，类似"[][]"的结果输不出来，因为不符合判断条件。详见代码。
5 const int maxn = 105; 6 const int inf = 0x3f3f3f3f; 7 char str[maxn]; 8 int dp[maxn][maxn]; 9 10 bool match(char a, char b){ 11 return (a=='('&&b==')') || (a=='['&&b==']'); 12 } 13 14 int dfs(int l, int r){ 15 if (l > r) 16 return dp[l][r] = 0; 17 if (l == r) 18 return dp[l][r] = 1; 19 if (dp[l][r] != inf) 20 return dp[l][r]; 21 int ans = dp[l][r]; 22 if (match(str[l], str[r])) 23 ans = min(ans, dfs(l+1, r-1)); 24 for (int i=l; i<r; ++i) 25 ans = min(ans, dfs(l, i)+dfs(i+1, r)); 26 return dp[l][r] = ans; 27 } 28 29 void print(int l, int r){ 30 if (l > r) 31 return ; 32 if (l == r){ 33 if (str[l]=='(' || str[r]==')') 34 printf("()"); 35 else 36 printf("[]"); 37 return ; 38 } 39 int ans = dp[l][r]; 40 if (match(str[l], str[r]) && ans==dp[l+1][r-1]){ 41 putchar(str[l]); 42 print(l+1, r-1); 43 putchar(str[r]); 44 return ; 45 } 46 for (int i=l; i<r; ++i) 47 if (ans == dp[l][i]+dp[i+1][r]){ 48 print(l, i); 49 print(i+1, r); 50 return ; 51 } 52 }
