> 感觉思路应该是：保存输入在数组b[100]中，建立一个二维A[100][100],A[i][j]表示b[i]~b[j]之间需要添加括号的最小数目。然后自底向上DP到A[0][strlen(b)-1]就可以了，为啥就是不对呢？
> 贴下代码：
> #include <stdio.h>
> #include <string.h>
> #include <math.h>
> 
> void p(int i, int j);
> 
> int C[100][100];
> int A[100][100];
> char b[100];
> int l = 0, i, j, k, tmp;
> 
> int main(void)
> {
> 	while(gets(b))
> 	{
> 		l = strlen(b);
> 		for(i = l-1; i>=0; --i)
> 		{
> 			A[i][i] = 1;
> 			for(j = i+1; j<l; ++j)
> 			{
> 				if(( (b[i]=='(') && (b[j]==')') )||( (b[i]=='[') && (b[j]==']')))
> 				{
> 					if((j-1)<(i+1))
> 						A[i][j] = 0;
> 					else
> 						A[i][j] = A[i+1][j-1];
> 					C[i][j] = -1;
> 				}
> 				else
> 				{
> 					A[i][j]=pow(2,31)-1;
> 					for(k = i; k<j; ++k)
> 					{
> 						tmp = A[i][k]+A[k+1][j];
> 						if(tmp<A[i][j])
> 						{
> 							A[i][j]=tmp;
> 							C[i][j]=k;
> 						}
> 					}
> 				}
> 			}
> 		}
> 		p(0,l-1);
> 		printf("\n");
> 	}
> 	return 0;
> }
> 
> void p(int i, int j)
> {
> 	if(i>j)
> 		return;
> 	else if(i==j)
> 	{
> 		switch(b[i])
> 		{
> 		case '(':;
> 		case ')':
> 			printf("()");
> 			break;
> 		case '[':;
> 		case ']':
> 			printf("[]");
> 			break;
> 		}
> 	}
> 	else
> 	{
> 		if(C[i][j]==-1)
> 		{
> 			printf("%c",b[i]);
> 			p(i+1,j-1);
> 			printf("%c",b[j]);
> 		}
> 		else
> 		{
> 			p(i,C[i][j]);
> 			p(C[i][j]+1,j);
> 		}
> 	}
> }