POJ 2955 Brackets 括号匹配区间DP

题意：在一些括号中找到一个序列，里面的括号都两两配对。求序列最长长度。

区间DP，dp[i][j]为i~j的最大括号数，考虑第i个括号，有两种情况：不管i直接算dp[i + 1][j];找到和i匹配的右括号，分两边算并加起来，dp[i][j] = dp[i + 1][k - 1] + 2 + dp[k + 1][j]。

代码：

/* 
*  Author:      illuz  
*  Blog:        http://blog.csdn.net/hcbbt 
*  File:        poj2955.cpp 
*  Create Date: 2013-11-11 14:47:59 
*  Descripton:  intervel dp  
*/  
  
#include   
#include   
  
#define check(i, j) ((str[i] == '[' && str[j] == ']') || (str[i] == '(' && str[j] == ')'))  
#define max(a, b) ((a) > (b)   (a) : (b))  
  
const int MAXN = 110;  
char str[MAXN];  
int dp[MAXN][MAXN], n;  
  
int solve(int i, int j) {  
    if (dp[i][j]) return dp[i][j];  
    if (j <= i) return 0;  
    if (j == i + 1) {  
        if (check(i, j))  
            return dp[i][j] = 2;  
        else  
            return 0;  
    }  
  
    dp[i][j] = solve(i + 1, j);  
    for (int k = i + 1; k <= j; k++)  
        if (check(i, k))   
            dp[i][j] = max(dp[i][j], solve(i + 1, k - 1) + solve(k + 1, j) + 2);  
    return dp[i][j];  
}  
  
int main() {  
    while (scanf("%s", str) && strcmp(str, "end")) {  
        memset(dp, 0, sizeof(dp));  
        printf("%d\n", solve(0, strlen(str) - 1));  
    }  
    return 0;  
}

POJ 2955 Brackets 括号匹配 区间DP