POJ 2955 - Brackets

http://poj.org/problem?id=2955

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 [([])].

Input

The input test file will contain multiple test cases. Each input test case consists of a single line containing only the characters (, ), [, and ]; each input test will have length between 1 and 100, inclusive. The end-of-file is marked by a line containing the word “end” and should not be processed.

Output

For each input case, the program should print the length of the longest possible regular brackets subsequence on a single line.

Sample Input

((()))
()()()
([]])
)[)(
([][][)
end

Sample Output

6
6
4
0
6

http://hehejun.blogspot.com/2018/02/poj2955-brackets.html

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

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)

        int len = s.size();

        for(int j = 0; j < len; ++j)

        {

            for(int i = j - 1; i >= 0; --i)

            {

                //assue s[i] is not matched

                dp[i][j] = dp[i + 1][j];

                for(int k = i + 1; k <= j; ++k)

                {

                    if(s[i] == '(' && s[k] == ')' || s[i] == '[' && s[k] == ']')

                        dp[i][j] = max(dp[i + 1][k - 1] + dp[k + 1][j] + 2, dp[i][j]);

                }

            }

        }

        

        cout<<dp[0][len - 1]<<endl;

https://blog.csdn.net/discreeter/article/details/51151247

题意：给一串由()[]四个字符组成的字符串，求最大匹配个数

思路：定义dp[i][j]为从i到j的最大匹配个数，当s[i]和s[j]相匹配时，显然有dp[i][j] = dp[i+1][j-1] + 2，然后依次枚举i到j之间的中间值dp[i][j] = max(dp[i][j], dp[i][k] + dp[k+1][j])

    char s[N];

    int dp[N][N];

    while(scanf(" %s", s), strcmp(s, "end"))

    {

        memset(dp, 0, sizeof dp);

        int len = strlen(s);

        for(int l = 2; l <= len; l++) /*枚举区间长度*/

        {

            for(int i = 0; i <= len - l; i++)/*区间起始位置*/

            {

                int j = i + l - 1; /*区间截止位置*/

                if((s[i] == '(' && s[j] == ')') || (s[i] == '[' && s[j] == ']'))

                    dp[i][j] = dp[i+1][j-1] + 2;

                for(int k = i; k < j; k++) /*枚举更新最大值*/

                    dp[i][j] = max(dp[i][j], dp[i][k] + dp[k+1][j]);

            }

        }

        printf("%d\n", dp[0][len-1]);

要求匹配括号不可交叉，即([)]这种不计入

因为不计交叉情况，转移就很直白。

枚举区间长度l，转移为

if( (str[i] == '(' && str[i+l-1] == ')')

 || (str[i] == '[' && str[i+l-1] == ']') ) 

    dp[i][i+l-1] = max(dp[i][i+l-1],dp[i+1][i+l-2]+2);

//合并相邻区间最长括号匹配数

for(int j = i; j < i+l; ++j)

    dp[i][i+l-1] = max(dp[i][i+l-1],dp[i][j]+dp[j+1][i+l-1]);