[POJ]1141 Brackets Sequence

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.

思路和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)，代码如下：