原题：AcWing1070

思路分析

我们注意到，这个题目其实与(密码脱落)是比较相似的。从当前字符串变成目标字符串需要添加最少字符的数量就等价于当前字符串变成最大目标字符串需要去掉字符的数量，即至少添加最少字符等价于总数量-最大目标字符串的长度

括号前后的配对其实就是构造回文串。但是在此之外，例如()[]这种情况也属于满足要求的串，所以我们还需要枚举分界点（类似石子合并）

1.状态表示

f[i][j]表示原串中$[i, j]$之间的所有满足要求的子序列括号串的集合，我们要求的属性就是长度的最大值。

2.状态计算

对于f[i][j]这个集合，我们可以整体划分为两个状态，分别是s[i]与s[j]能匹配和s[i]与s[j]不能匹配。

• 能匹配：答案很显然，就是$f[l+1][r-1]+2$。
• 不能匹配：例如()[]这种情况，我们就要现在左边选若干个$k=j-i+1$，这样就分为两段$[l,k]$和$[k+1,r]$，取最大就可以搞定了。

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

const int N = 110;
int n;
string s;
int f[N][N];

//判断是否是一对括号
bool check(char a, char b) {
    if (a == '(' && b == ')') return true;
    if (a == '[' && b == ']') return true;
    return false;
}

int main() {
    cin >> s;
    n = s.size();

    for (int len = 2; len <= n; len++) {
        for (int L = 0; L + len - 1 < n; L++) {
            int R = L + len - 1;
            f[L][R] = 0;

            // 情况1：首尾匹配
            if (check(s[L], s[R])) {
                f[L][R] = max(f[L][R], 2 + f[L + 1][R - 1]);
            }

            // 情况2：枚举分割点
            for (int k = L; k < R; k++) {
                f[L][R] = max(f[L][R], f[L][k] + f[k + 1][R]);
            }
        }
    }
    cout << n - f[0][n - 1] << endl;
    return 0;
}

容易发现是区间dp，考虑一个区间可能怎么更新而来，显然有两种可能：

• 有两个合法的区间合并，枚举中点即可
• 还有一个容易忽视的转移，嵌套也是合法的所以[l,r]=([l+1,r-1]) or [[l+1,r-1]]