题目描述：给一些中括号和小括号，让你添加尽量少的括号，使其合法。

    动态规划，dp[i][j]为对子字符串i~j进行合理化所需的最小步骤。

    若str[i]和str[j]正好构成一对，则dp[i][j] = dp[i 1][j - 1],路径设置为ans[i][j] = -1;

    否则用k属于i ~ j - 1 分割 子串i~j 为 i ~ k 和 k 1 ~ j

    dp[i][j] = min(dp[i][j], dp[i][k] dp[k 1][j]); 路径设置为ans[i][j] = k;

    i > j dp[i][j] = 0;

    i == j dp[i][j] = 1 // 一个括号时需要补足另一个，代价为1

    输出的时候对ans递归调用即可。

    代码如下

    #include<iostream>
#include<string>
using namespace std;
int dp[105][105];
string str;
char s[105];
int ans[105][105];
void output(int i, int j)
{
    if (i > j)
        return;
    if (i == j)
    {
        if (str[i] == '(' || str[i] == ')')
            printf("()");
        else
            printf("[]");
    }
    else if (ans[i][j] == -1)
    {
        cout << str[i];
        output(i 1, j - 1);
        cout << str[j];
    }
    else
    {
        output(i, ans[i][j]);
        output(ans[i][j] 1, j);
    }
}
int dg(int i, int j)
{
    if (i > j) dp[i][j] = 0;
    else if (i == j) dp[i][j] = 1;
    if (dp[i][j] != -1)
        return dp[i][j];
 dp[i][j] = 200000000;
    if (str[i] == '(' && str[j] == ')' || str[i] == '[' && str[j] == ']')
    {
        dp[i][j] = dg(i 1, j - 1);
        ans[i][j] = -1;
    }
    for(int k = i; k <= j - 1; k )
        if (dg(i, k) dg(k 1, j) < dp[i][j])
        {
            dp[i][j] = dg(i, k) dg(k 1, j);
            ans[i][j] = k;
        }
    return dp[i][j];
}
int main()
{
    char c;
    int pos = 0;
    while((c = getchar()) != '\n')
        s[pos ] = c;
    s[pos] = '\0';
    str = s;
    memset(dp, -1, sizeof(dp));
    if (pos == 0)
    {
        cout << endl;
        return 0;
    }
    dg(0, pos - 1);
    output(0, pos - 1);
    return 0;
}