dp[i][j]代表i->j区间内最多的合法括号数

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

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

dp[i][j]=max{dp[i][k]+dp[k+1][j]};

注意要对于区间的最值合并

ac代码：

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

int check(char a,char b)

{

    if(a=='('&&b==')')

    return 1;

    if(a=='['&&b==']')

    return 1;

    return 0;

}

int main()

{

    char str[111];

    int dp[111][111],i,j,k,len;

    while(scanf("%s",str)!=EOF)

    {

        if(!strcmp(str,"end"))

        break;

        len=strlen(str);

        memset(dp,00,sizeof(dp));

        for(k=1;i<len;k++)  ////表示区间长度，从0-len更新

        {

            for(i=0,j=k;j<len;i++,j++)

            {

                if(check(str[i],str[j]))

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

                for(int x=i;x<j;x++)  // //区间最值合并

                {

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

                }

            }

        }

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

    }

    return 0;

}