1070. 括号配对

上一题POJ 2955 Brackets求的是满足完美匹配的最大括号数量，而这题问的是使所有括号完美匹配需要添加的最小括号数量。

要使添加的括号尽量少，我们需要使原来的括号序列尽可能多得匹配，先求最大匹配数量，那么还剩下一些没有匹配的括号，我们就需要依次加上一个括号使它们得到匹配。

状态表示：
(f(i,j))：区间([i,j])至少添加的字符个数。

边界：
(f(i,i)=1)。

const int N=110;
int f[N][N];
string s;
int n;

bool match(int x,int y)
{
    return s[x] == '(' && s[y] == ')' || s[x] == '[' && s[y] == ']';
}

int main()
{
    cin>>s;

    n=s.size();
    for(int i=n-1;i>=0;i--)
        for(int j=i;j<n;j++)
        {
            if(i == j) f[i][j]=1;
            else
            {
                f[i][j]=INF;
                if(match(i,j)) f[i][j]=f[i+1][j-1];
        
                for(int k=i;k<j;k++)
                    f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]);
            }
        }
            

    cout<<f[0][n-1]<<endl;
    //system("pause");
    return 0;
}