POJ - 2955 brackets interval DP

subject link

Ideas

Classical interval $dp$ The topic of transfer mode has been given

consider $dp[i][j]$ It means that $[i,j]$ The number of bracket pairs that can be matched in the interval
State shift
$f[i][j]=f[i+1][j-1]+check(i,j);$
$f[i][j]=max(f[i][j],f[i][k]+f[k+1][j]);$

Code

int f[110][110];
string s;
bool chk(int i,int j){
    
    if((s[i] == '[' && s[j] == ']')||(s[i]=='(' && s[j]==')')) return true;
    return false;
}

signed main()
{
    
    
    while(cin >> s){
    
        if(s == "end") break;
        mem(f,0);
        int le = s.size();
        forr(len,2,le){
    

            for(int i = 0;i+len-1<le;i++){
    
                int j = i+len-1;
                f[i][j] = f[i+1][j-1]+chk(i,j);
                for(int k = i;k<j;k++) f[i][j] = max(f[i][j],f[i][k]+f[k+1][j]);
            }
        }
        cout << f[0][le-1]*2 << endl;
    }
    return 0;