POJ 1141 Brackets Sequence G++ 區間dp 背

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
using namespace std;
//英語       看博友分析     抄博友程式       區間dp      背
int dp[108][108];//dp[i][j]表示區間i~j比對添加括号後區間最小長度
int v[108][108];
string s;
void dfs(int l,int r)
{
	//cout<<l<<" "<<r<<endl;
	if(l>r)//抄博友程式 
	{
		return;
	} 
	if(l==r)
	{
		if(s[l]=='('||s[l]==')')
		{
			cout<<"()";
		}else if(s[l]=='['||s[l]==']')
		{
			cout<<"[]";
		}
		return ;
	}
	if(v[l][r]==-1)
	{
		if(s[l]=='(')
		{
			cout<<"(";
			dfs(l+1,r-1);
			cout<<")";
		}else if(s[l]=='[')
		{
			cout<<'[';
			dfs(l+1,r-1);
			cout<<']';
		}
	}else//抄博友程式 
	{
		dfs(l,v[l][r]);
		dfs(v[l][r]+1,r); 
	}
}
int main()
{
	memset(dp,0,sizeof(dp));//沒掌握 
	cin>>s;
	int n=s.size();
	for(int i=0;i<n;i++)
	{
		dp[i][i]=2;
	}
	for(int l=1;l<n;l++)//背 
	{
		for(int i=0;i+l<n;i++)
		{
			dp[i][i+l]=0x3f3f3f3f;//背 
			for(int k=i;k<i+l;k++)//抄博友程式 
			{
				//cout<<i<<"|"<<i+l<<"="<<i<<"|"<<k<<"+"<<k+1<<"|"<<i+l<<endl; 
				if(dp[i][i+l]>dp[i][k]+dp[k+1][i+l])
				{
					dp[i][i+l]=dp[i][k]+dp[k+1][i+l];//抄博友程式 
					v[i][i+l]=k;
				}				
			}
			if((s[i]=='('&& s[i+l]==')')||(s[i]=='[' && s[i+l]==']'))
			{
				if(dp[i][i+l]>dp[i+1][i+l-1]+2)
				{
					dp[i][i+l]=dp[i+1][i+l-1]+2;
					v[i][i+l]=-1;
				}
			}			
		}
	} 
	dfs(0,n-1);
	cout<<endl;
	return 0;
}