题目链接。

题目大意：给定一个只含有括号'(' ')' '[' ']'的长度在100以内的字符串，输出以这个字符串为子序列的最短合法括号串。相似题目（我没有UVA账号）

学校oj上通过（但是老师造的数据很水qwq）POJ不过，没调出来。

#include<iostream>
#include<cstring>
using namespace std;
typedef long long ll;

string s;
int n;
int dp[105][105],num[105][105];//断点记录
void dfs(int l,int r){
	if(l==r){
		if(s[l-1]=='('||s[l-1]==')'){
			cout<<"()";
		}else{
			cout<<"[]";
		}
		return ;
	}else if(l>r){
		return ;
	}else{
		if(num[l][r]==0){
			cout<<s[l-1];
			dfs(l+1,r-1);
			cout<<s[r-1];
		}else{
			dfs(l,num[l][r]);
			dfs(num[l][r]+1,r);
		}
	}
}
int main(){
	cin>>s;
	n=s.size();
	memset(dp,0x3f,sizeof(dp));
	for(int i=1;i<=n;i++) dp[i][i]=1;
	for(int i=1;i<n;i++){
		if((s[i-1]=='('&&s[i]==')')||(s[i-1]=='['&&s[i]==']')){
			dp[i][i+1]=0;
			num[i][i+1]=0;
		}else{
			dp[i][i+1]=2;
			num[i][i+1]=i;
		}
	}
	for(int k=3;k<=n;k++){
		for(int i=1;i<=n-k+1;i++){
			int j=i+k-1;
			if((s[i-1]=='['&&s[j-1]==']')||(s[i-1]=='('&&s[j-1]==')')) dp[i][j]=dp[i+1][j-1],num[i][j]=0;
			for(int w=i;w<j;w++){
				if(dp[i][j]>=dp[i][w]+dp[w+1][j]){
					dp[i][j]=dp[i][w]+dp[w+1][j];
					num[i][j]=w;
				}
			}
		}
	}
	//cout<<s.size()+dp[1][n];
	dfs(1,n);
	return 0;
}
/*

*/