AcWing 1070. 括号配对
原题链接
中等
作者:
麻衣学姐的可爱小男友
,
2023-05-27 11:44:11
,
所有人可见
,
阅读 127
#include<bits/stdc++.h>
using namespace std;
int arr[1025];
int f[1005][105];
int is_match(char a,char b){
if(a=='('&&b==')') return 1;
if(a=='['&&b==']') return 1;
return 0;
}
int main(){
int i,j,k;
string s;
cin>>s;
int length=s.size();
for(i=0;i<length;i++) f[i][i]=1;
for(int len=1;len<=length;len++){
for(i=0;i<length;i++){
j=i+len;
if(j>=length) break ;
f[i][j]=0x3f3f3f3f;
if(is_match(s[i],s[j])){
f[i][j]=f[i+1][j-1];
}
f[i][j]=min(f[i][j],f[i+1][j]+1);
f[i][j]=min(f[i][j],f[i][j-1]+1);
for(k=i;k<j;k++){
f[i][j]=min(f[i][k]+f[k+1][j],f[i][j]);
}
}
}
cout<<f[0][length-1];
return 0;
}