括號序列問題，劉汝佳黑書上的動態規劃第一題，真是經典問題。不過這道題要輸出方案。

動態規劃狀態設定 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;
}