区间dp

算是经典的区间dp问题

但是我上来写错了,,,唉

我的思路错了,还是要小心啊

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int dp[110][110];
char s[110];
int n;
bool check(char s1,char s2){
    return (s1=='('&&s2==')')||(s1=='['&&s2==']');
}
int main(){
    while (scanf("%s",s+1)){
        if (s[1]=='e')break;
        n = strlen(s+1);
        memset(dp,0,sizeof(dp));
        for (int p=2;p<=n;++p){
            for (int i=1,j=i+p-1;j<=n;++i,++j){
                if (check(s[i],s[j]))dp[i][j]=dp[i+1][j-1]+2;
                for (int k=i;k<j;++k)dp[i][j]=max(dp[i][k]+dp[k+1][j],dp[i][j]);
            }
        }
        printf("%d\n",dp[1][n]);
    }
}