区间DP（括号序列，uva1626）

发现动态规划，记忆化搜索，bfs之类的寻找最优解的算法，往往会有一些寻找最优解过程中的记录。通过观察这些记录，我们能寻到一些蛛丝马迹，从而找到最优解是如何一步一步形成的。因此可以打印决策过程，或者说可以还原我们是如何一步一步找到答案的，比如打印最短路径，又或者如此题中打印解。

以前BFS还能打印路径就觉得很神奇了。

今天碰到区间DP，用递归的方法还原路径，学到了。

关于记忆化搜索与动态规划的关系，9，10,11楼说的话：  http://tieba.baidu.com/p/1161996521

#include<bits/stdc++.h>
#define maxn 110
#define INF 0X3F3F3F3F
using namespace std;

char str[maxn];
int dp[maxn][maxn];
int len;

void print(int l,int r)
{
    if(l>r) return;
    if(l==r)
    {
        if(str[l]=='('||str[l]==')') printf("()");
        else printf("[]");
        return;
    }
    if(((str[l]=='('&&str[r]==')')||(str[l]=='['&&str[r]==']'))&&dp[l][r]==dp[l+1][r-1])
    {
        printf("%c",str[l]);
        print(l+1,r-1);
        printf("%c",str[r]);
        return;
    }
    for(int k=l;k<r;k++)
        if(dp[l][r]==dp[l][k]+dp[k+1][r])
        {
            print(l,k);
            print(k+1,r);
            return;
        }
}

int main()
{
    for(int i=0;i<maxn;i++) dp[i][i]=1;
    int t;
    scanf("%d",&t);
    gets(str+1);
    while(t--)
    {
        gets(str+1);
        gets(str+1);
        len=strlen(str+1);
        for(int i=2;i<=len;i++)
            for(int j=1;j+i-1<=len;j++)
            {
                int l=j;
                int r=j+i-1;
                if((str[l]=='('&&str[r]==')')||(str[l]=='['&&str[r]==']')) dp[l][r]=dp[l+1][r-1];
                else dp[l][r]=INF;
                for(int k=l;k<r;k++) dp[l][r]=min(dp[l][r],dp[l][k]+dp[k+1][r]);
            }
        print(1,len);
        puts("");
        if(t) puts("");
    }
    return 0;
}