学步园

这道题是黑书上的一个例题，不过没有给出最终输出的串，但是可以通过递归把最后的串输出

首先我们定义d[i][j] 为从i位置到j位置的串匹配所需的最少步数

那么当s[i] = '('&& s[j] =')' 或者s[i] = '['&&s[j] =']'时，显然d[i][j] = minI(d[i][j], d[ i + 1][ j - 1])

然后当s[i]和s[j]不匹配的时候，就要对串进行增加，达到匹配

然后我们还可以将串进行拆分，拆成两部分

for k=i to j-1

d[i][j] = min(d[i][j], d[i][k] + d[k + 1][j])

这样才能保证d[i][j]是最小的。

并且，计算d[i][j]时，前提是知道了d[i + 1][j - 1],d[i][j - 1] d[i + 1][j]

所以必须从j-i最小的开始算，逐渐递增

题目求的是最后的串，所以就要开另一个辅助数组v,

v[i][j]记录了一些信息，

当v[i][j] = -1时表示s[i],s[j]已经匹配

当v[i][j]为非负时，表示串在该位置(v[i][j]的值)处进行过拆分，就要分别递归进入这两个串中

#include <iostream>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cmath>
#include <ctime>
#define INF 1000000000
using namespace std;
char s[205];
int d[105][105];
int v[105][105];
void print(int i, int j)
{
    if(i > j) return;
    if(i == j)
    {
        if(s[i] == '(' || s[i] == ')')
        printf("()");
        else printf("[]");
    }
    else
    {
        if(v[i][j] == -1)
        {
            printf("%c", s[i]);
            print(i + 1, j - 1);
            printf("%c", s[j]);
        }
        else
        {
            print(i, v[i][j]);
            print(v[i][j] + 1, j);
        }
    }
}
int main()
{
    while(gets(s) != 0)
    {
        int n = strlen(s);
        memset(d, 0, sizeof(d));
        memset(v, 0, sizeof(v));
        for(int i = 0; i < n; i++)
        d[i][i] = 1;
        for(int p = 1; p < n; p++)
        {
            for(int i = 0; i < n - p; i++)
            {
                int j = i + p;
                d[i][j] = INF;
                if((s[i] == '(' && s[j] == ')') || (s[i] == '[' && s[j] == ']'))
                {
                    if(d[i][j] > d[i + 1][j - 1])
                    {
                        d[i][j] = d[i + 1][j - 1];
                        v[i][j] = -1;
                    }
                }
                for(int k = i; k < j; k++)
                {
                    if(d[i][j] > d[i][k] + d[k + 1][j])
                    {
                        d[i][j] = d[i][k] + d[k + 1][j];
                        v[i][j] = k;
                    }
                }
            }
        }
        print(0, n - 1);
        printf("\n");
    }
    return 0;
}