Brackets Sequence POJ

状态转移方程：
i > j , f [ i ] [ j ] = 0 ; （空串不需要补括号）
i = j , f [ i ] [ j ] = 1 ; （单个括号需要补一个括号）
if s [ i ] match s [ j ] , f [ i ] [ j ] = f [ i + 1 ] [ j - 1 ] ;
else f [ i ] [ j ] = min( f [ i ] [ j ] , f [ i ] [ k ] + f [ k + 1 ] [ j ] ) ; （分割区间，递归子问题）

打印答案见代码注释

数据有空格，scanf过不了
AC代码

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
const int N=1e2+5;
const int inf=0x3f3f3f3f;
int f[N][N],path[N][N];
char s[N];
void print_str(int l,int r)
{
    //printf("%d %d %d
",l,r,path[l][r]);
    if(l>r) return; 
    if(l==r) //只剩一个括号没配对，则打印整套括号
    {
        if(s[l]=='('||s[l]==')') printf("()");
        else printf("[]");
        return;
    }
    if(path[l][r]==-1) //当前l r 配对，区间缩小（path是分界点）
    {
        putchar(s[l]);
        print_str(l+1,r-1);
        putchar(s[r]);
    }
    else // 递归到左分界点区间和右分界点区间
    {
        print_str(l,path[l][r]);
        print_str(path[l][r]+1,r);
    }
}
bool match(char x,char y)
{
    if(x=='('&&y==')'||x=='['&&y==']') return 1;
    return 0;
}
void init(int n)
{
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(i<j) f[i][j]=inf;
            else if(i==j) f[i][j]=1;
            else f[i][j]=0;
        }
    }
    memset(path,-1,sizeof(path) );
}
int main()
{
    while(gets(s+1) )
    {
        int n=strlen(s+1);
        init(n);
        for(int len=1;len<n;len++)
        {
            for(int i=1;i+len<=n;i++)
            {
                int j=i+len;
                if(match(s[i],s[j])&&f[i][j]>f[i+1][j-1])
                {
                    f[i][j]=f[i+1][j-1];
                    path[i][j]=-1;
                }
                for(int k=i;k<j;k++)
                {
                    if(f[i][j]>f[i][k]+f[k+1][j])
                    {
                        path[i][j]=k;
                        f[i][j]=f[i][k]+f[k+1][j];
                    }
                }
            }
        }
        //printf("%d
",f[1][n] );
        print_str(1,n);
        putchar('
');
    }
    return 0;
}