[POJ]2955 Brackets

We give the following inductive definition of a “regular brackets” sequence:

• the empty sequence is a regular brackets sequence,
• if s is a regular brackets sequence, then (s) and [s] are regular brackets sequences, and
• if a and b are regular brackets sequences, then ab is a regular brackets sequence.
• no other sequence is a regular brackets sequence

For instance, all of the following character sequences are regular brackets sequences:

(), [], (()), ()[], ()[()]

while the following character sequences are not:

(, ], )(, ([)], ([(]

Given a brackets sequence of characters a₁a₂ … a_n, your goal is to find the length of the longest regular brackets sequence that is a subsequence of s. That is, you wish to find the largest m such that for indices i₁, i₂, …, i_m where 1 ≤ i₁ < i₂ < … < i_m ≤ n, a_i1a_i2 … a_im is a regular brackets sequence.

Given the initial sequence ([([]])], the longest regular brackets subsequence is [([])].

找最长合法匹配括号子序列的问题。根据题目的定义，一个合法的子序列满足以下条件：

1. 空串是合法的
2. 如果s是合法的，那么[s]和(s)也是合法的
3. 如果a和b是合法的，那么ab也是合法的
4. 除此之外都是不合法的

第三点暗示了可以用区间DP来解决这个问题。我们用DP[i][j]来表示子串s[i,j]中最长的合法子序列。那么我们有递推公式：

• DP[i][j] = DP[i + 1][j], if there is no match for s[i]
• DP[i][j] = max(DP[i + 1][k - 1] + 2 + DP[k + 1][j]), if i < k <= j && s[k] matches s[i]

第二个递推公式就是利用定义的第二条来将字符串分割成左右两部分，我们枚举所有的分割点，从而找到能让合法序列最长的分割方式，这就是子串s[i,j]最长的合法子串。假设输入串长度为n，时间和空间复杂度均为O(n^2)，代码如下：