This post is written in Chinese. Please consider using Google Translate

括号序列问题，刘汝佳黑书上的动态规划第一题，真是经典问题。不过这道题要输出方案。

动态规划状态设定 F[i,j]表示子序列[i,j]要成为括号序列所需添加的最小括号数目。

状态转移方程 F[i,j]=Min { F[i+1,j-1] (S[i]与S[j]匹配) //剥离一层匹配的括号 F[i+1,j] + 1 (S[i]为左半括号) //在结尾添加对应的右半括号 F[i,j-1] + 1 (S[j]为右半括号) //在开头添加对应的左半括号 F[i,k] + F[k+1,j] //从第k位分裂开 }

时间复杂度 O(N^3)

在动态规划状态转移的过程中记录前驱状态与添加括号的位置，然后递归输出括号序列。

以下是程序代码

#include <iostream>

using namespace std;

const int MAX=201;
const int INF=0x7FFFFFFF;

struct T
{
    int pos,fi,fj,gi,gj;
    char addition;
};

char S[MAX];
int N;
int F[MAX][MAX];
T G[MAX][MAX];

void init()
{
    freopen("1183.in","r",stdin);
    freopen("1183.out","w",stdout);
    scanf("%s",S+1);
    N=strlen(S+1);
}

inline char opp(char a)
{
    switch(a)
    {
        case '(': return ')';
        case ')': return '(';
        case '[': return ']';
    }
    return '[';
}

void peel(int i,int j)
{
    if (i+1<=N && j-1>=1)
    {
        if ((S[i]=='(' && S[j]==')') || (S[i]=='[' && S[j]==']'))
        {
            if (F[i+1][j-1]<F[i][j])
            {
                F[i][j]=F[i+1][j-1];
                G[i][j].fi=i+1;    G[i][j].fj=j-1;    G[i][j].pos=-1;
            }
        }
    }
}

void addhead(int i,int j)
{
    if (S[j]==')' || S[j]==']')
    {
        if (F[i][j-1]+1<F[i][j])
        {
            F[i][j]=F[i][j-1]+1;
            G[i][j].fi=i;    G[i][j].fj=j-1;    G[i][j].pos=1;
            G[i][j].addition=opp(S[j]);
        }
    }
}

void addtail(int i,int j)
{
    if (S[i]=='(' || S[i]=='[')
    {
        if (F[i+1][j]+1<F[i][j])
        {
            F[i][j]=F[i+1][j]+1;
            G[i][j].fi=i+1;    G[i][j].fj=j;    G[i][j].pos=2;
            G[i][j].addition=opp(S[i]);
        }
    }
}

void split(int i,int j)
{
    for (int k=i;k<j;k++)
    {
        if (F[i][k]+F[k+1][j]<F[i][j])
        {
            F[i][j]=F[i][k]+F[k+1][j];
            G[i][j].fi=i; G[i][j].fj=k;
            G[i][j].gi=k+1; G[i][j].gj=j;
            G[i][j].pos=-2;
        }
    }
}

void dynamic()
{
    int i,j;
    for (i=N;i>=1;i--)
    {
        for (j=i;j<=N;j++)
        {
            F[i][j]=INF;
            split(i,j);
            peel(i,j);
            addtail(i,j);
            addhead(i,j);
        }
    }
}

void print(int i,int j)
{
    if (i>j) return;
    if (G[i][j].pos==-1)
    {
        putchar(S[i]);
        print(i+1,j-1);
        putchar(S[j]);
    }
    else if (G[i][j].pos==-2)
    {
        print(G[i][j].fi,G[i][j].fj);
        print(G[i][j].gi,G[i][j].gj);
    }
    else if (G[i][j].pos==1)
    {
        putchar(G[i][j].addition);
        print(G[i][j].fi,G[i][j].fj);
        putchar(S[j]);
    }
    else
    {
        putchar(S[i]);
        print(G[i][j].fi,G[i][j].fj);
        putchar(G[i][j].addition);
    }
}

int main()
{
    init();
    dynamic();
    print(1,N);
    return 0;
}