题目链接：点击打开
题意：给出一串的只有‘（’ ‘）’ ‘[‘ ‘]’四种括号组成的串，让你求解需要最少添加括号数让串中的所有括号完全匹配。
分析：定义dp [ i ] [ j ] 为串中第 i 个到第 j 个括号的最大匹配数目

那么我们假如知道了 i 到 j 区间的最大匹配，那么i+1到 j+1区间的是不是就可以很简单的得到。

那么 假如第 i 个和第 j 个是一对匹配的括号那么dp [ i ] [ j ] = dp [ i+1 ] [ j-1 ] + 2 ;

那么我们只需要从小到大枚举所有 i 和 j 中间的括号数目，然后满足匹配就用上面式子dp，然后每次更新dp [ i ] [ j ]为最大值即可。

更新最大值的方法是枚举 i 和 j 的中间值，然后让 dp[ i ] [ j ] = max ( dp [ i ] [ j ] , dp [ i ] [ d ] + dp [ d+1 ] [ j ] ) ;

代码如下：

//
//Created by BLUEBUFF 2016/1/10
//Copyright (c) 2016 BLUEBUFF.All Rights Reserved
//

#pragma comment(linker,"/STACK:102400000,102400000")
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/hash_policy.hpp>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cmath>
#include <cstdio>
#include <time.h>
#include <cstdlib>
#include <cstring>
#include <complex>
#include <sstream> //isstringstream
#include <iostream>
#include <algorithm>
using namespace std;
//using namespace __gnu_pbds;
typedef long long LL;
typedef pair<int, LL> pp;
#define REP1(i, a, b) for(int i = a; i < b; i++)
#define REP2(i, a, b) for(int i = a; i <= b; i++)
#define REP3(i, a, b) for(int i = a; i >= b; i--)
#define CLR(a, b) memset(a, b, sizeof(a))
#define MP(x, y) make_pair(x,y)
template <class T1, class T2>inline void getmax(T1 &a, T2 b) { if (b>a)a = b; }
template <class T1, class T2>inline void getmin(T1 &a, T2 b) { if (b<a)a = b; }
const int maxn = 210;
const int maxm = 1e5+5;
const int maxs = 10;
const int maxp = 1e3 + 10;
const int INF  = 1e9;
const int UNF  = -1e9;
const int mod  = 1e9 + 7;
const int rev = (mod + 1) >> 1; // FWT
const double PI = acos(-1);
//head
char s[maxn];
int dp[maxn][maxn]; //i,j区间最大的匹配数
int main()
{
    while(scanf("%s", s) != EOF){
        if(strcmp(s, "end") == 0) break;
        CLR(dp, 0);
        int le = strlen(s);
        for(int k = 1; k < le; k++){
            for(int i = 0; i + k - 1 < le; i++){
                int j = i + k;
                if((s[i] == '(' && s[j] == ')') || ((s[i] == '[' && s[j] == ']'))) dp[i][j] = dp[i+1][j-1] + 2;
                for(int d = i; d < j; d++){
                    dp[i][j] = max(dp[i][j], dp[i][d] + dp[d+1][j]);
                }
            }
        }
        cout << dp[0][le - 1] << endl;
    }
    return 0;
}