【区间DP】POJ2955.Brackets

题目

POJ2955.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_1,a_2 \dots 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_1,i_2,\dots,i_m$ where $1\leq i_1<i_2<\dots <i_m \leq n$ , $a_{i1},a_{i2} … a_{im}$ is a regular brackets sequence.

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

题目就是给出一个字符串，求合法的子序列，注意，可以分开，连续的话是另外的题目

思路

区间DP，我们另dp[i][j]代表字符串从i到j内我们所需要的值，也就是最长的合法子序列，那我们得出递推转移公式：
如果第i个和第j个匹配的话，那么就表示区间 $[i,j]$ 的值可以从 $[i+1,j-1]$ 而来： $dp[i][j]=dp[i+1][j-1]+2$
那么我们还得有一个转移就是一个区间 $[i,j]$ 的值从两个子区间拼接而成，也就是： $dp[i][j]=max(dp[i][j],dp[i][p]+dp[p+1][j])$

代码

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstdlib>
using namespace std;
string s;
const int N = 207;
int dp[N][N];
int main()
{
    while (cin>>s)
    {
        if (s=="end") return 0;
        memset(dp,0,sizeof(dp));
        int len=s.size();
        for (int k=1;k<len;k++)
        {
            for (int i=0,j=k;j<len;i++,j++)
            {
                if ((s[i]=='('&&s[j]==')')||(s[i]=='['&&s[j]==']'))
                    dp[i][j]=dp[i+1][j-1]+2;
                for (int d=i;d<j;d++)
                    dp[i][j]=max(dp[i][j],dp[i][d]+dp[d+1][j]);
            }
        }
        cout<<dp[0][len-1]<<endl;
    }
}