括号序列的最小合法化：区间动态规划与路径记录

### 问题描述

我们需要解决的问题是：给定一个由括号组成的序列，通过添加最少数量的括号，使其成为一个合法的括号序列，并输出该合法序列。合法括号序列是指每个左括号都有对应的右括号匹配，且匹配关系正确。

#### 数据范围
- 字符串长度 n 不超过 100。

### 涉及算法

本题主要使用区间动态规划（Interval DP）来解决。区间DP是一种特殊的动态规划方法，适用于处理区间上的问题，通过逐步扩大区间的范围来更新状态。

### 解题思路

我们定义 dp[i][j] 表示将区间 [i, j] 内的括号序列变成合法序列所需的最少添加括号数。具体的状态转移方程如下：

1. **初始化**：对于单个字符的区间，如果该字符是左括号或右括号，则需要添加一个对应的右括号或左括号。
2. **状态转移**：对于区间 [i, j]，我们有两种情况：
- 如果 s[i] 和 s[k] 是一对匹配的括号（例如 '(' 和 ')' 或 '[' 和 ']'），则可以将区间 [i+1, k-1] 和 [k+1, j] 分别处理，此时 dp[i][j] = dp[i+1][k-1] + dp[k+1][j]。
- 如果没有找到匹配的括号，则直接在 s[i] 处添加一个对应的括号，dp[i][j] = dp[i+1][j] + 1。
3. **路径记录**：为了输出最终的合法序列，我们需要记录路径信息。path[i][j] 记录了区间 [i, j] 内匹配的括号位置。

### 代码实现

以下是完整的 C++ 实现代码：

```cpp
#include
using namespace std;
const int N = 105;
char s[N];
int dp[N][N], path[N][N];

void print(int l, int r) {
if (l > r) return;
if (path[l][r] == -1) {
if (s[l] == '(' || s[l] == ')') printf("()");
else printf("[]");
print(l + 1, r);
} else {
printf("%c", s[l]);
print(l + 1, path[l][r] - 1);
printf("%c", s[path[l][r]]);
print(path[l][r] + 1, r);
}
}

int main() {
while (~scanf("%s", s)) {
int n = strlen(s);
memset(dp, 0, sizeof(dp));
for (int len = 1; len <= n; len++) {
for (int i = 0, j = i + len - 1; j dp[i][j] = dp[i + 1][j] + 1; // s[i] 需要匹配一个括号
path[i][j] = -1; // 记录路径
for (int k = i + 1; k <= j; k++) { // 小序列更新大序列
if ((s[i] == '(' && s[k] == ')') || (s[i] == '[' && s[k] == ']'))
if (dp[i][j] > dp[i + 1][k - 1] + dp[k + 1][j]) {
dp[i][j] = dp[i + 1][k - 1] + dp[k + 1][j];
path[i][j] = k; // 记录路径
}
}
}
}
print(0, n - 1);
printf("\n");
}
return 0;
}
```