这个题目最初写的时候用的完全是yls上课的那道例题的思路，结果怎么都是错的，想了很久终于想通了。

这道题和那道回文的例题不同之处在于括号的匹配可能存在下列两种情况
1.((())) 该种情况类似回文 匹配数为3
2.()()() 但这种情况则与回文不同 然而匹配数也是3个
而第二种情况也导致每次进行状态计算时是对每个内部区间取一个最大值

基本思路

添加若干的字符使其达到匹配的目的 等价于 将不匹配的字符去除 使得字符串达到匹配的目的
所以这题只是计算出已配完成的括号数 再用总长度减去 就是不匹配的字符长度 即为答案

关于DP的状态表示和状态计算

1.关于状态表示
a.集合： L,R区间内括号匹配数目的集合
b.属性： max

2.状态计算
划分为2个部分
a.选择L,R端点 f[L][R]=f[L+1][R-1]+1;(s[L]==s[R])
b.不全选L,R端点 f[L][R]=max(f[L][R],f[L][k]+f[k+1][R]);
对于a部分比较好理解 L,R端点均选择时如果相等则结果+1
对于b部分
以左端点为例 不选L的可能性包含于L+1~R的所有集合中 同理只选右端点 和两个端点都不选的情况也是一样的

以下为完整代码

C++ 代码

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;

const int N=110;

//第一维代表左端 第二维代表右端点
//值代表当前区间已经匹配的括号数
int f[N][N];    
char s[N];

int main()
{
    scanf("%s",s);
    int n=strlen(s);

    for(int len=1;len<=n;len++)
        for(int i=0;i+len-1<n;i++)
        {
            int l=i;
            int r=l+len-1;

            if((s[l]=='('&&s[r]==')')||(s[l]=='['&&s[r]==']'))
                f[l][r]=f[l+1][r-1]+1;

            for(int k=l;k<r;k++)
                f[l][r]=max(f[l][r],f[l][k]+f[k+1][r]);
        }

    printf("%d",n-f[0][n-1]*2);


    return 0;
}