poj 2955 区间dp

题意：给你一串()[]括号，要你求出这串括号的最大匹配个数。如'('与')'匹配，为2个，'['与']'匹配，为2个

思路：区间dp

状态方程：

if(s[i]=='('&&s[j]==')'||s[i]=='['&&s[j]==']')
     dp[i][j]=dp[i+1][j-1]+2;
dp[i][j]=max{dp[i][k]+dp[k+1][j]};（k>i&&k<j）
代码：（g++）
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stdlib.h>
#include <string.h>
#include <iomanip>
#define N 10005<<1
#define INF 10000000
#define LL long long
#define eps 10E-9
#define mem(a)  memset(a,0,sizeof(a))
#define mem1(a)  memset(a,-1,sizeof(a))
#define w(a)   while(a)
#define s(a)   scanf("%d",&a)
#define ss(a,b)   scanf("%d%d",&a,&b)
#define sss(a,b,c)   scanf("%d%d%d",&a,&b,&c)
#define PI acos(-1.0)
using namespace std;
int dp[101][101];
int main(){
     string s;
     w(cin>>s){
     mem(dp);
     if(s[0] == 'e') break;
     int len = s.length();
     for(int i=1; i<len; i++){
        for(int j=0,k=i; k<len; j++,k++){
            if(s[j] == '('&& s[k] == ')' || s[j] == '[' && s[k] == ']') dp[j][k] = dp[j+1][k-1] + 2;
            for(int l=j; l<k ; l++) dp[j][k] = max(dp[j][k], dp[j][l] + dp[l+1][k]);
            }
     }
     cout<<dp[0][len-1]<<endl;
   }
   return 0;
}