上一題POJ 2955 Brackets求的是滿足完美比對的最大括号數量,而這題問的是使所有括号完美比對需要添加的最小括号數量。
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;
}