思路与算法

dp[l][r]表示把原串区间补成合法括号串所需的最少插入数。单个字符补1个，空区间补0。若两个端点能配成()或[]，可一起保留并使用内部dp；另枚举所有分界k，将左右两段分别补齐后连接，取最小值。按区间长度递增计算。

正确性说明

任意合法串或者是两个非空合法串连接，或者最外层的一对括号包住内部合法串。若原区间端点互为匹配括号，就可采用后一种构造；如果最优补全中端点不互相配对，则在合法结构的分解中可找到一个分界，使两端分别处于不同子结构，代价由两段相加。单字符只能与新增括号匹配，需1次。递推覆盖所有结构且每个候选都可构成合法补全，归纳得最小值。

复杂度

共有O(L²)区间，每区间枚举O(L)分界，时间O(L³)，空间O(L²)。二维数组零初始化O(L²)、单字符初始化O(L)，都计入总界。L<100，空输入行直接输出0，不访问不存在的数组位置。

易错点

只能插入，不能删除或交换原字符；()与[]不能混配。([)]需要补字符，不能因左右括号个数相等就返回0。独立答案使用最大合法括号子序列的配对数：每个未配对原字符补一个，结果为L-最大配对字符数。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
int main() {
    string s;
    getline(cin, s);
    if (!s.empty() && s.back() == '\r')
        s.pop_back();
    int n = s.size();
    if (n == 0) {
        cout << 0 << '\n';
        return 0;
    }
    vector<vector<int>> dp(n, vector<int>(n));
    for (int i = 0; i < n; ++i)
        dp[i][i] = 1;
    for (int len = 2; len <= n; ++len)
        for (int l = 0; l + len <= n; ++l) {
            int r = l + len - 1;
            dp[l][r] = n;
            if ((s[l] == '(' && s[r] == ')') || (s[l] == '[' && s[r] == ']'))
                dp[l][r] = len == 2 ? 0 : dp[l + 1][r - 1];
            for (int k = l; k < r; ++k)
                dp[l][r] = min(dp[l][r], dp[l][k] + dp[k + 1][r]);
        }
    cout << dp[0][n - 1] << '\n';
}