题意分析

1. 首先明确合法括号序列的定义：
   • 空序列是合法的。
   • 如果(S)是合法的，那么((S))和([S])是合法的。
   • 如果(A)和(B)是合法的，那么(AB)是合法的。
2. 题目要求给定一个由((, ), [, ])组成的序列，找到最短的合法括号序列，使给定序列是它的子序列。
3. 输入是最多包含(100)个括号的一行字符，输出是满足条件的最短合法括号序列。

解题思路

1. 状态定义：
   • dp[i][j]表示字符串(s)中从第(i)个字符到第(j)个字符的子串需要添加的最少括号数。
   • path[i][j]用于记录从(i)到(j)的最优分割点或配对情况。
2. 初始化：
   • 对于单个字符，dp[i][i]=1，因为单个括号本身是不合法的，至少需要添加一个括号才能使其合法。
   • 对于其他情况，dp[i][j]初始化为无穷大（这里用(0x3f3f3f3f)表示）。
3. 状态转移：
   • 对于长度为(2)的子串：
     • 如果(s[i]'(' && s[j]')')或者(s[i]'[' && s[j]']')，那么dp[i][j]=dp[i + 1][j - 1]，并且path[i][j]=-1表示这两个括号可以配对。
     • 如果(i + 1 == j)，即两个相邻括号，那么dp[i][j]=0，path[i][j]=-1，因为它们本身就构成了一个合法的括号对。
   • 对于长度大于(2)的子串：
     • 遍历所有可能的分割点(k)（(l\leq k\lt r)），如果dp[l][k]+dp[k + 1][r]\lt dp[l][r]，则更新dp[l][r]=dp[l][k]+dp[k + 1][r]，并记录分割点path[l][r]=k。
4. 输出结果：
   • 通过dfs函数根据path数组递归输出最短合法括号序列。
   • 如果path[l][r]==-1，说明(s[l])和(s[r])可以配对，先输出(s[l])，递归处理中间部分，再输出(s[r])。
   • 如果path[l][r]!= -1，说明需要在(k)处分割，分别递归输出两部分。

复杂度分析

1. 时间复杂度：
   • 有三层循环，第一层循环遍历子串长度(len)，从(2)到(n)，第二层循环遍历子串的起始位置(l)，第三层循环遍历分割点(k)。
   • 对于长度为(n)的字符串，总的时间复杂度为(O(n^3))。
2. 空间复杂度：
   • 使用了二维数组dp[maxn][maxn]和path[maxn][maxn]，空间复杂度为(O(n^2))。

代码实现

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

const int maxn = 105;
int dp[maxn][maxn], path[maxn][maxn];
char s[maxn];

void dfs(int l, int r) {
    if (l > r) return;
    if (l == r) {
        if (s[l] == '(' || s[l] == ')') cout << "()";
        else cout << "[]";
        return;
    }
    if (path[l][r] == -1) {
        cout << s[l];//先输出左端点,
        dfs(l + 1, r - 1);//再输出中间,
        cout << s[r];//最后输出右端点。
    }
    else {
        int k = path[l][r];//分两部分输出。
        dfs(l, k);
        dfs(k + 1, r);
    }
}

int main() {
    int n;
    // 使用fgets函数代替gets函数
    while (fgets(s + 1, maxn, stdin)!= NULL) {
        // 去掉fgets读取的换行符
        s[strcspn(s + 1, "\n") + 1] = '\0';
        n = strlen(s + 1);
        memset(dp, 0x3f, sizeof(dp));
        memset(path, 0, sizeof(path));
        for (int i = 1; i <= n; i++) dp[i][i] = 1;//初始化：自己当然初始化为1,其他初始化为无穷大。
        for (int len = 2; len <= n; len++) {
            for (int l = 1; l <= n - len + 1; l++) {
                int r = len + l - 1;
                if ((s[l] == '(' && s[r] == ')') || (s[l] == '[' && s[r] == ']')) {
                    if (dp[l + 1][r - 1] < dp[l][r]) {
                        dp[l][r] = dp[l + 1][r - 1];
                        path[l][r] = -1;
                    }
                    else if (l + 1 == r) {
                        dp[l][r] = 0;
                        path[l][r] = -1;
                    }
                }
                for (int k = l; k < r; k++) {
                    if (dp[l][k] + dp[k + 1][r] < dp[l][r]) {
                        dp[l][r] = dp[l][k] + dp[k + 1][r];
                        path[l][r] = k;
                    }
                }
            }
        }
        dfs(1, n);
        cout << endl;
    }
    return 0;
}