Brackets

　

brackets

1.dp[i][j]表示从i到j匹配的括号的最大数量。

2.转移方程dp[i][j] = max(dp[i][j],dp[i+1][k-1]+dp[k+1][j]+2);

表示当第k个括号和第i个括号匹配时，即ss[i] == ss[k]

括号数量为第i+1~k-1的括号数量和第k+1~j的括号数量+2

#include<iOStream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
string ss;
int dp[105][105];

int main()
{
    char ss[105];
    while(~scanf("%s",ss+1))
    {
        if(strcmp(ss+1,"end") == 0)
        break;
        int len = strlen(ss+1);
        memset(dp,0,sizeof(dp));

        for(int i = len-1 ; i>=1 ; i--)
        {
            for(int j = i+1 ; j<=len ;j++)
            {
                dp[i][j] = dp[i+1][j];
                if(ss[i] == '('||ss[i]=='[')
                {
                    for(int k = i+1 ; k <= j ; k++)
                    {
                        if(ss[i]=='('&&ss[k]==')'||ss[i]=='['&&ss[k]==']')
                        dp[i][j] = max(dp[i][j],dp[i+1][k-1]+dp[k+1][j]+2);
                    }   
                }

            }
        }


        cout<<dp[1][len]<<endl;
    }

    return 0;
}

相关阅读

用栈解决----括号匹配问题(MatchBrackets)

问题：给出一个字符数组，判断里边的括号是否匹配。 分析：首先我们要确定用什么方法来解决这个问题，然后再进一步分析过程。 我们可以用