poj1141括号匹配（区间dp+递归打印路径）

题目描述：给出一串由‘（‘）’‘ [ ' ' ] '组成的串，让你输出添加最少括号之后使得括号匹配的串。

思路：

i-j表示的是一条序列的开始和结束,dp[ i ][ j ]表示子串s[ i~j ] 需要添加的数量。

思想是不断分割小区间，当出现（X）时，应该转移到x，即从dp（i，j)转移到dp（i+1，j-1）

如果为单个字符，则dp[ i ][ j ] = 1;(i == j) 

打印：算出最优的地方 1、如果可以直接往里转移，则 dp[ i ][ j ] == dp[ i+1 ][ j-1 ];把s[i]和s[j]打印了，再向里递归print(i+1, j-1)；

                                    2、s[i]!=s[j]，则直接去找i-j之间的最优点k进行切分，然后递归

代码：

#include <cstdio>
#include <algorithm>
#include <vector>
#include <string>
#include <cstring>
#include <iostream>

using namespace std;
const int inf=0x3f3f3f3f;
string s;
int d[110][110],value[110][110],len;

void print(int i,int j){//递归输出
    if(i>j) return;
    else if(i==j){
        if(s[i]==')'||s[i]=='(') printf("()");
        if(s[i]==']'||s[i]=='[') printf("[]");
    }
    else if(value[i][j]==-1){
        printf("%c",s[i]);
        print(i+1,j-1);
        printf("%c",s[j]);
    }
    else{
        print(i,value[i][j]);
        print(value[i][j]+1,j);
    }
    return;
}

int main(){
	while(getline(cin,s)){
		//注意整行读入，有可能是空格
        memset(d,0,sizeof(d));
        len=(int)s.length();
        for(int i=0; i<=len; i++) d[i][i]=1;
		for(int tem=1; tem<len; tem++){//
			for(int i=0; i<=len-tem; i++){
				int j=tem+i;
				d[i][j]=inf;
				if((s[i]=='('&&s[j]==')')||(s[i]=='['&&s[j]==']')){
					d[i][j]=d[i+1][j-1];
					value[i][j]=-1;//匹配标志
				}
				for(int k=i; k<j; k++){
					if(d[i][j]>d[i][k]+d[k+1][j]){//更新i-j的最小答案
						d[i][j]=d[i][k]+d[k+1][j];
						value[i][j]=k;//找到中间更新的点
					}
				}
			}
		}
        print(0,len-1);
        printf("\n");
    }

}