学步园

设原括号序列为S1 S2 … Sn。

如果S1和 Sn匹配，则相当于求S2 … Sn-1的括号匹配情况。这时最终的匹配结果是：先打印S1，再打印S2 … Sn-1的括号匹配结果，最后打印Sn。

如果S1和 Sn不匹配，怎么办呢？如果把S1 S2 … Sn从中间某个位置（比如Sk）分成两截，问题就变成S1 … Sk和Sk+1 … Sn的情况了。也就是说，把原问题划分成了两个结构相同的子问题。那么，具体从哪划分呢？好像没有什么信息可用，那就从1…n对k进行枚举。因为最终要打印结果，所以还要记录k的值。这时最终的结果是：先打印S1 … Sk的匹配情况，再打印Sk+1 … Sn的匹配情况。

设dp( i, j )表示Si … Sj匹配时，所要加入的最少括号数。

状态转换方程：

dp( i, j ) = dp( i+1, j-1 )                               ifS1和 Sn匹配

dp( i, j ) = Min( dp( i, k ) + dp( k+1, j ) ),   其中 i <= k < j    ifS1和 Sn不匹配

下图是字符串( [ ( ]的计算过程。

编程实现：算法是有了，不过具体的编程实现还是有点小技巧。嘿嘿，当前主要是针对初学者来说，大牛可完全无视之。

初始条件。当i==j时，dp( i, j ) = ？想想实际情况，只剩下一个括号时，不管它是什么当然不匹配啦。所以必须找到它的另一半才行，故dp( i, i ) = 1

计算顺序。应该沿Z型计算，即i、j之间相差1，i、j之间相差2，…

打印结果。使用递归打印。

#include <iostream>
#include <string>
#include <cstring>
using namespace std;

#define MAX 105
#define INF 999999
string strin;
int dp[MAX][MAX];
int pos[MAX][MAX];

void solve()
{
	int size=(int)strin.size();
	for(int i=0;i<size;i++) dp[i][i]=1;
	for(int k=1;k<size;k++)
	{
		for(int i=0,j=k+i;i<size&&j<size;i++,j++)
		{
			dp[i][j]=INF;
			if((strin[i]=='('&&strin[j]==')')||(strin[i]=='['&&strin[j]==']'))
			{
				dp[i][j]=dp[i+1][j-1];
				pos[i][j]=-1;
			}
			//注意：这里不要用else  
           		//因为要求最小，所以即使比配也要进行下面的处理：例如[][]  
            		//枚举tmp,求划分str的最佳位置   
			for(int tmp=i;tmp<j;tmp++)
			{
				if(dp[i][j]>dp[i][tmp]+dp[tmp+1][j])
				{
					dp[i][j]=dp[i][tmp]+dp[tmp+1][j];
					pos[i][j]=tmp;
				}
			}
		}
		
	}
}

void print(int begin,int end)
{
	if(begin==end)
	{
		if(strin[begin]=='('||strin[begin]==')') cout<<"()";
		if(strin[begin]=='['||strin[begin]==']') cout<<"[]";
	}
	if(begin<end)
	{
		if(pos[begin][end]==-1)
		{
			cout<<strin[begin];
			print(begin+1,end-1);
			cout<<strin[end];
		}
		else
		{
			int tmp=pos[begin][end];
			print(begin,tmp);
			print(tmp+1,end);
		}
	}
}
int main()
{
	cin>>strin;
	solve();
	print(0,strin.size()-1);
	cout<<endl;
	return 0;
}

原文链接  http://blog.csdn.net/sj13051180/article/details/6668499