Let us define a regular brackets sequence in the following way:

1. Empty sequence is a regular sequence.

2. If S is a regular sequence, then (S) and [S] are both regular sequences.

3. If A and B are regular sequences, then AB is a regular sequence.

For example, all of the following sequences of characters are regular brackets sequences:

(), [], (()), ([]), ()[], ()[()]

And all of the following character sequences are not:

(, [, ), )(, ([)], ([(]

Some sequence of characters '(', ')', '[', and ']' is given.
You are to find the shortest possible regular brackets sequence, that
contains the given character sequence as a subsequence. Here, a string
a1 a2 ... an is called a subsequence of the string b1 b2 ... bm, if
there exist such indices 1 = i1 < i2 < ... < in = m, that aj =
bij for all 1 = j = n.

The input file contains at most 100 brackets (characters '(',
')', '[' and ']') that are situated on a single line without any other
characters among them.

Write to the output file a single line that contains some regular
brackets sequence that has the minimal possible length and contains the
given sequence as a subsequence.

([(]

()[()]

题意：给你一个不完整的括号序列，要求你添加最少的括号，使其可以构成一个左右互相匹配的完整的序列。
思路分析：开始想了个贪心，但是是不对
　　　　正解是区间 dp，dp[i][j]表示区间 i - j 内添加最小数量的括号可以使其匹配，然后在转移的过程中判断一下当前区间的括号是否可以匹配上，如果可以此时的值则等于其内部区间的值，否则则在加一层 for去判断
　　　　输出的地方采用递归的方式去输出，比较经典的一个题
代码示例：

char s[105];

int dp[105][105], path[105][105];

void print(int l, int r){

    if (l > r) return;

    if (l == r){

        if (s[l] == '(' || s[l] == ')') printf("()");

        if (s[l] == '[' || s[l] == ']') printf("[]");

        return;

    }

    if (path[l][r] == -1){

        putchar(s[l]);

        print(l+1, r-1);

        putchar(s[r]);

    }

    else{

        print(l, path[l][r]);

        print(path[l][r]+1, r);

    }

}

int main() {

    //freopen("in.txt", "r", stdin);

    //freopen("out.txt", "w", stdout);

    while(gets(s+1) != NULL){

        int n = strlen(s+1);

        memset(dp, 0, sizeof(dp));

        for(int i = 1; i <= n; i++) dp[i][i] = 1;

        for(int len = 2; len <= n; len++){ // 区间长度

            for(int i = 1; i <= n; i++){

                int j = i+len-1;

                if (j > n) break;

                dp[i][j] = inf;

                if ((s[i]=='('&&s[j]==')') || (s[i]=='['&&s[j]==']')){

                    dp[i][j] = dp[i+1][j-1];

                    path[i][j] = -1;

                }

                for(int k = i; k < j; k++){

                    if (dp[i][k]+dp[k+1][j] < dp[i][j]){

                        dp[i][j] = dp[i][k]+dp[k+1][j];

                        path[i][j] = k;

                    }

                }

          //      printf("+++ %d %d %d \n", i, j, dp[i][j]);

            }

        }

        print(1, n);

        //printf("%d\n", dp[1][n]);

        printf("\n");

    }

    return 0;

}

/*

([(]

*/