形式化题目

给定一个仅由小括号 () 与中括号 [] 构成的字符串 $s$。 合法括号序列（GBE）定义如下：

1. 空串是合法括号序列；
2. 若 $A$ 是合法括号序列，则 $(A)$ 与 $[A]$ 也是合法括号序列；
3. 若 $A$ 与 $B$ 都是合法括号序列，则拼接串 $AB$ 也是合法括号序列。

求在原串中插入最少数量的字符，使其变为合法的括号序列。

正解

思路

根据合法括号序列的归纳定义，任何非空的合法括号串只有两种基本形成形式：

1. 外层包裹：形如 $(A)$ 或 $[A]$，即最外层的两个字符互相匹配，内部子串自身也是合法括号序列；
2. 中间拼接：形如 $AB$，即可以从某一处断开，拆分为两个非空的合法括号序列拼接而成。

这表明子串的最优配对方案具有明显的最优子结构和重叠子问题性质，因此可以使用区间动态规划求解。

1. 状态定义

设 $dp[i][j]$ 表示将子串 $s[i \dots j]$ 补齐为合法括号序列所需添加的最少字符数（$0 \leqslant i \leqslant j < n$）。

2. 边界与初始化

• 单个字符无法自行配对，必须补上对应的另一个括号才能合法，因此：
  $$dp[i][i] = 1 \quad (0 \leqslant i < n)$$
• 当 $i > j$ 时，对应空串，代价为 $0$。在实现中未访问的位置默认初始化为 $0$ 即可。

3. 状态转移

对于区间 $[i, j]$（长度 $len \geqslant 2$）：

1. 两端匹配：若两端字符 $s[i]$ 与 $s[j]$ 能够闭合配对（即 ( 与 )，或 [ 与 ]），则可以利用这两个字符作为最外层括号，代价等于内部子串 $s[i+1 \dots j-1]$ 的代价：
   $$\text{cost} = dp[i+1][j-1]$$
   若两端不配对，则置为 $+\infty$。
2. 区间分割：考虑将区间在位置 $k$（$i \leqslant k < j$）切分成两半，分别补齐后再拼接：
   $$\text{split\_cost} = \min_{i \leqslant k < j} \{dp[i][k] + dp[k+1][j]\}$$
   注：当 $k = i$ 时，$dp[i][i] + dp[i+1][j] = 1 + dp[i+1][j]$，即单独为左端点字符补齐一个配对；当 $k = j-1$ 时同理。因此单侧补齐的情况已被分割点枚举完全覆盖。

综合上述两种转移方式，状态转移方程为：

按区间长度由小到大递推计算，最终答案即为 $dp[0][n-1]$（若原串为空串则答案为 $0$）。

代码

Python 版：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-07-05 21:47
# update_at: 2026-07-05 21:47

import sys

MATCH = {"(": ")", "[": "]"}


def min_insertions_to_regular(s: str) -> int:
    """求将括号序列补全为合法括号序列（GBE）所需增加的最少字符数。"""
    n = len(s)
    if n == 0:
        return 0

    dp = [[0] * n for _ in range(n)]
    for i in range(n):
        dp[i][i] = 1

    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            cost = dp[i + 1][j - 1] if MATCH.get(s[i]) == s[j] else float("inf")
            split_cost = min(dp[i][k] + dp[k + 1][j] for k in range(i, j))
            dp[i][j] = min(cost, split_cost)

    return dp[0][n - 1]


def solve() -> None:
    data = iter(sys.stdin.buffer.read().split())
    s = next(data, b"").decode()
    print(min_insertions_to_regular(s))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-05 09:17
 * update_at: 2026-10-05 09:17
 */
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 105;
const ll INF = 0x3f3f3f3f3f3f3f3fLL; // 转移中的无穷大，表示当前无法匹配

char s[MAXN];    // 输入的括号串，下标从 0 开始
ll n;            // 括号串长度
ll dp[MAXN][MAXN]; // dp[i][j] 表示把子串 s[i..j] 补齐为合法括号序列所需添加的最少字符数

// 判断左右两个字符能否配成一对括号。
bool matched(char left, char right) {
    if (left == '(' && right == ')') return true;
    if (left == '[' && right == ']') return true;
    return false;
}

void solve() {
    if (n == 0) {
        cout << 0 << "\n";
        return;
    }

    // 长度为 1 的区间自己无法配对，必须补一个括号
    for (ll i = 0; i < n; i++) {
        dp[i][i] = 1;
    }

    // 按区间长度从小到大递推，保证子区间已算好
    for (ll len = 2; len <= n; len++) {
        for (ll i = 0; i + len - 1 < n; i++) {
            ll j = i + len - 1;
            ll best = INF;

            // 两端匹配：用 s[i]、s[j] 作最外层括号，代价等于内部子串的代价
            if (matched(s[i], s[j])) {
                best = dp[i + 1][j - 1]; // i >= j-1 时该位置没算过，全局默认为 0，正好是空串代价
            }

            // 枚举分割点，把区间拆成 s[i..k] 与 s[k+1..j] 两段分别补齐再拼接
            for (ll k = i; k < j; k++) {
                ll candidate = dp[i][k] + dp[k + 1][j];
                if (candidate < best) {
                    best = candidate;
                }
            }

            dp[i][j] = best;
        }
    }

    cout << dp[0][n - 1] << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> s;
    n = strlen(s);

    solve();

    return 0;
}

复杂度

• 时间复杂度：共有 $O(n^2)$ 个子区间状态，计算每个状态需要枚举 $O(n)$ 个分割点，总时间复杂度为 $O(n^3)$。对于 $n < 100$，运算量约在 $1.6 \times 10^5$ 次量级，能在几十毫秒内完成。
• 空间复杂度：需要维护一个大小为 $n \times n$ 的二维 DP 数组，空间复杂度为 $O(n^2)$。

总结

• 本题是区间动态规划的经典入门问题，核心在于抓住合法括号序列的递归定义：要么最外层两端闭合匹配，要么中间存在分割点拼接。
• 将两端字符匹配作为直接继承转移，将所有可能的分割点合并作为区间松弛，涵盖了所有最小补齐方案。

图示解析

以样例输入 [])（长度为 $3$，$s[0]=\text{`[`}, s[1]=\text{`]`}, s[2]=\text{`)`}$）为例说明 DP 表的填表与转移过程：

1
2
3
4
5       j=0     j=1     j=2
       '['     ']'     ')'
i=0 '['  1       0       1
i=1 ']'  -       1       2
i=2 ')'  -       -       1

• 长度 1：$dp[0][0]=1, dp[1][1]=1, dp[2][2]=1$。
• 长度 2：
  • $s[0 \dots 1] = \text{`[]`}$：$s[0]$ 与 $s[1]$ 匹配，两端代价为 $dp[1][0]=0$；分割点 $k=0$ 时代价为 $dp[0][0]+dp[1][1]=2$。取最小值得到 $dp[0][1]=0$。
  • $s[1 \dots 2] = \text{`])`}$：两端不匹配，分割点 $k=1$ 代价为 $dp[1][1]+dp[2][2]=1+1=2$。因此 $dp[1][2]=2$。
• 长度 3：
  • $s[0 \dots 2] = \text{`[])`}$：两端 [ 与 ) 不匹配，枚举分割点：
    • $k=0$：$dp[0][0] + dp[1][2] = 1 + 2 = 3$；
    • $k=1$：$dp[0][1] + dp[2][2] = 0 + 1 = 1$。
    • 取最小值得到 $dp[0][2] = 1$。

只需在最右侧补齐一个小括号 ( 变成 []()，增加 $1$ 个字符即满足条件。