動(dòng)態(tài)規(guī)劃，具體的狀態(tài)方程看劉汝佳的黑書。
#include <stdio.h>
#include <string.h>

const int LEN = 105;
const int MAX = 0x7fffffff;

int dp[LEN][LEN];

int cup ( char str[] )
{

    int max = 0;
    int len = strlen ( str );

    for ( int i=0; i<len; i++ )
    {
        dp[i][i] = 1;
        if ( i!=0 )
        {
            dp[i][i-1] = 0;
        }
    }

    for ( int p=1; p<len; p++ )
    {
        int i, j;
        for ( i=0; i<len-p; i++ )
        {
            j = i+p;
            dp[i][j] = MAX;
            if ( str[i]=='('&&str[j]==')'||str[i]=='['&&str[j]==']' )
            {
                if ( dp[i][j]>dp[i+1][j-1] )
                {
                    dp[i][j] = dp[i+1][j-1];
                }
            }
            else
            {
                if ( str[i]=='('||str[i]=='[' )
                {
                    if ( dp[i][j]>dp[i+1][j]+1 )
                    {
                        dp[i][j] = dp[i+1][j]+1;
                    }
                }
                if ( str[j]==')'||str[j]==']' )
                {
                    if ( dp[i][j]>dp[i][j-1]+1 )
                    {
                        dp[i][j] = dp[i][j-1]+1;
                    }
                }
            }
            for ( int k=i; k<j; k++ )
            {
                if ( dp[i][j]>dp[i][k]+dp[k+1][j] )
                {
                    dp[i][j] = dp[i][k]+dp[k+1][j];
                }
            }

            if ( max<j-i+1-dp[i][j] )
            {
                max = j-i+1-dp[i][j];
            }
        }
    }

    return max;
}

int main ()
{

    char str[LEN];

    while ( gets ( str )&&strcmp ( "end", str ) )
    {
        if ( str[0]!='\0' )
        {
            printf ( "%d\n", cup ( str ) );
        }
        else
        {
            printf ( "0\n" );
        }
    }
    return 0;
}