感觉思路应该是：保存输入在数组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);
		}
	}
}

• 少算了很多子问题 (24) try99 2007-08-12 10:37:40
  • Re:少算了很多子问题 (45) stoundmire 2008-04-10 19:05:55
    • Re:少算了很多子问题 (35) GARYLAI 2008-06-13 16:09:34
• dp的顺序不对会造WA (1426) fantasyorg 2008-05-22 11:59:12
• Re:感觉很标准的DP题啊，为啥就是做不对呢？ (114) lynxpengpeng 2008-05-25 17:23:47
• Re:感觉很标准的DP题啊，为啥就是做不对呢？ (1440) hookun 2008-08-05 13:07:40
• Re:感觉很标准的DP题啊，为啥就是做不对呢？ (1426) lbeny 2008-09-01 15:45:35