DP

PS: 记忆化搜索

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 105;
const int INF = 0x3fffffff;
char str[N];
int dp[N][N];
int path[N][N];
bool done[N][N];
using namespace std;

int bracket(int i, int j) {
    if(done[i][j]) return dp[i][j];
    int ans = INF;
    if(i > j) return 0;
    else if(i==j) return 1;
    else {
        if((str[i]==‘(‘&&str[j]==‘)‘) || (str[i]==‘[‘&&str[j]==‘]‘)) {
            ans = min(ans, bracket(i+1, j-1));
        }
        if(str[i]==‘(‘||str[i]==‘[‘) {
            ans = min(ans, bracket(i+1, j)+1);
        }
        if(str[j]==‘)‘||str[j]==‘]‘) {
            ans = min(ans, bracket(i, j-1)+1);
        }
        for(int k = i; k < j; k++) {
            ans = min(ans, bracket(i, k)+bracket(k+1, j));
        }
    }
    done[i][j] = true;
    return dp[i][j] = ans;
}

int main()
{
    while(gets(str))
    {
        memset(done, false, sizeof(done));
        int n = strlen(str);
        if(n==0) {
            printf("\n");
            continue;
        }
        int ans = bracket(0, n-1);
        printf("%d\n", ans);
    }
    return 0;
}
/***
(([)
(]((]][]
([(]
((([])
***/

DP,布布扣,bubuko.com

DP

原文：http://blog.csdn.net/achiberx/article/details/23603307