刚刚开始用dp 不太熟悉..  不知道怎么在求解过程中构造最优解..  

  这个题 我求出了最少需要加多少个括号.. 但是不知道怎么记录添加括号的位置..

搜索函数:

int checkMsg(int head,int tail)//  (0,msgLen-1)
{
	int i;
	int temp;
	int posi =-1;
	int ans =MAX;
	
	if(head>tail)
		return 0;
	
	if(head==tail)
		return 1;

	if(proCount[head][tail]!=MAX)
		return proCount[head][tail];
	
	if( (oriMsg[head]=='('&&oriMsg[tail]==')')||
		(oriMsg[head]=='['&&oriMsg[tail]==']') )
	{
		if(proCount[head+1][tail-1]==MAX)
			proCount[head+1][tail-1] =checkMsg(head+1,tail-1);
		
		if(ans>proCount[head+1][tail-1])
			ans  =proCount[head+1][tail-1];
	}
	
	if(oriMsg[head]=='('||oriMsg[head]=='[')
	{
		if(proCount[head+1][tail]==MAX)
			proCount[head+1][tail] =checkMsg(head+1,tail);
		
		if(ans>(proCount[head+1][tail]+1))
		{
			ans  =proCount[head+1][tail]+1;
			posi =head;
		}
	}
	
	if(oriMsg[tail]==')'||oriMsg[tail]==']')
	{
		if(proCount[head][tail-1]==MAX)
			proCount[head][tail-1] =checkMsg(head,tail-1);
		
		if(ans>(proCount[head][tail-1]+1))
		{
			ans  =proCount[head][tail-1]+1;
			posi =tail;
		}
	}
	
	for(i=head;i<tail;i++)
	{
		temp =checkMsg(head,i)+checkMsg(i+1,tail);
		if(ans>temp) 
			ans =temp;
	}
	
	proCount[head][tail] =ans;
	addPosi[posi] =true;

	return proCount[head][tail];
	
}

• Re:求助 记忆化搜索怎么构造最优解啊.. (1436) zjpb_xy 2008-03-30 16:32:21
  • Re:求助 记忆化搜索怎么构造最优解啊.. (14) zjpb_xy 2008-03-30 16:34:01
• Re:求助 记忆化搜索怎么构造最优解啊.. (1233) a903428320 2009-04-18 17:47:01