>   刚刚开始用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:求助 记忆化搜索怎么构造最优解啊.. (14) zjpb_xy 2008-03-30 16:34:01