学步园

题意：

给你一个只包括大小括号的串，一个合法串的定义如下：

1.空串是合法的；

2.若s为合法的，则 [s] (s) 也为合法的；

3.若 a，b为合法的 ， ab 也是合法的。

给你一个长度小于100的串，请加入最少的括号使其合法化。

解法：

区间dp，记录转移路径，类似 poj 2955，不过将dp[i][j]的意义改为使子段变为合法的最少插入数，O(n³)。

要点：

1. 初始化的时候，这题与poj 2955 的状态意义不一样，所以初始化时有效区间为inf（因为要求最小的），无效为0（方便转移时边界的处理）；

2.边界处理，dp[i][i] 为边界 （区间长度最短），显然是1，因为一个半括号当且仅当加入一个为最优解；

3.对于区间长度为2时并且两个括号失配时的处理，直接是取中间空隙为中断点，因为这种情况需要插入两个括号，因此不需要特殊处理；

4.根据转移路径递归重构答案即可。

代码：

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

const int maxn = 105;
const int inf = 1<<29;
int dp[maxn][maxn];
int path[maxn][maxn];
string s;

bool match(char a, char b) {
    return (a=='('&&b==')') || (a=='['&&b==']');
}

void print(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];
        print(l+1, r-1);
        cout << s[r];
        return;
    }
    int k = path[l][r];
    print(l, k);
    print(k+1, r);
}

int main() {
    while(getline(cin,s)) {
        for(int i = 0 ; s[i] ; i++) {
            for(int j = 0 ; s[j] ; j++) {
                dp[i][j] = i < j ? inf:0;
            }
        }
        memset(path,-1,sizeof(path));

        for(int i = 0 ; s[i] ; i++)
            dp[i][i] = 1;
        for(int i = 0 ; s[i] ; i++) {
            for(int j = i-1 ; j >= 0 ; j--) {
                if(match(s[j],s[i])){
                    dp[j][i] = dp[j+1][i-1];
                }
                for(int k = j ; k < i ; k++){
                    if(dp[j][i] > dp[j][k]+dp[k+1][i]){
                        dp[j][i] = dp[j][k]+dp[k+1][i];
                        path[j][i] = k;
                    }
                }
            }
        }
        print(0, s.length()-1);
        cout << endl;
    }
    return 0;
}