UVA 1626 Brackets sequence ( DP 括弧匹配 )

UVa Online Judge
題目大意：給定一個括弧序列，可任意增加、插入括弧，求最少增加的情況下的合法括弧序列。
可以考慮遞迴，一個序列大致有三種情況可以處理，一種是它的外部是合法的，可以試著直接將外部刪去，第二種是在某個切割點分開的情況做分治，這就枚舉所有分割點，最後一種是序列長度只有 1，那麼直接增加另一邊使它合法就行了。這麼一來，只要令 dp( i, j )為序列 [ i, j )需要最少增加的括弧數，就能做到 O( N ^ 3 )。至於打印解序列的部分，一步一步根據狀態轉移式回朔到邊界，遞迴打印就可以了。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100 + 5;
const int INF = 1e9;

int n;
string s;
int memo[MAXN][MAXN];

int dp(int ql, int qr){ // [ ql, qr )
    if( ql == qr ) return 0;
    if( ql + 1 == qr ) return 1;
    if( memo[ql][qr] < INF ) return memo[ql][qr];
    for(int i = ql + 1; i < qr; ++i)
        memo[ql][qr] = min( memo[ql][qr], dp( ql, i ) + dp( i, qr ) );
    if( s[ql] == '(' && s[qr-1] == ')' ) 
        memo[ql][qr] = min( memo[ql][qr], dp( ql+1, qr-1 ) );
    if( s[ql] == '[' && s[qr-1] == ']' ) 
        memo[ql][qr] = min( memo[ql][qr], dp( ql+1, qr-1 ) );
    return memo[ql][qr];
}

bool match(char a, char b){
    if( a == '(' && b == ')' ) return true;
    if( a == '[' && b == ']' ) return true;
    return false;
}

void print(int ql, int qr){
    if( qr - ql <= 0 ) return;
    if( qr - ql == 1 ){
        if( s[ql] == '(' || s[ql] == ')' ) cout << "()";
        else cout << "[]";
        return;
    }
    if( match( s[ql], s[qr-1] ) && dp( ql, qr ) == dp( ql + 1, qr - 1 ) ){
        cout << s[ql]; print( ql+1, qr-1 ); cout << s[qr-1];
        return;
    }
    for(int i = ql + 1; i < qr; ++i)
        if( dp( ql, qr ) == dp( ql, i ) + dp( i, qr ) ){
            print( ql, i ); print( i, qr );
            return;
        }
}

int main(){
    ios::sync_with_stdio(false);
    int T; cin >> T; getline( cin, s );
    bool first = true;
    while( T-- ){
        if( first ) first = false;
        else cout << endl;
        getline( cin, s ); // eat blank line
        getline( cin, s );
        n = s.size();
        for(int i = 0; i <= n; ++i)
            for(int j = 0; j <= n; ++j)
                memo[i][j] = INF;
        dp( 0, n );
        print( 0, n );
        cout << endl;
    }
    return 0;
}