【区间DP && 记录路径】URAL - 1183 Brackets Sequence

Step1 Problem:

加入最少数量的括号使得这个括号序列合法，输出合法括号序列。
数据范围：
字符串长度n不超过100.

Step2 Involving algorithms:

区间dp

Step3 Ideas:

状态dp[i][j]：区间[i, j]需要最少数量的括号。
状态转移方程：
我们需要用满足序列 更新 满足序列 使得 满足序列需要的括号数越来越少。
区间范围从1-n，先求范围小，在求范围大，这样才满足 满足序列 更新 满足序列。
对于区间范围len
dp[i][j] = dp[i+1][j] + 1;//插入括号使得合法
dp[i][j] = min(dp[i][j], dp[i+1][k-1] + dp[k+1][j]);//其中s[i] 和 s[k]是配对括号，利用范围小序列更新范围大序列。
同时记录路径

Step4 Code:

#include<bits/stdc++.h>
using namespace std;
const int N = 105;
char s[N];
int dp[N][N], path[N][N];
void prit(int l, int r)
{
    if(l > r) return ;
    if(path[l][r] == -1)
    {
        if(s[l] == '(' || s[l] == ')') printf("()");
        else printf("[]");
        prit(l+1, r);
    }
    else
    {
        printf("%c", s[l]);
        prit(l+1, path[l][r] - 1);
        printf("%c", s[path[l][r]]);
        prit(path[l][r]+1, r);
    }
}
int main()
{
    while(~scanf("%s", s))
    {
        int n = strlen(s);
        memset(dp, 0, sizeof(dp));
        for(int len = 1; len <= n; len++)
        {
            for(int i = 0, j = i+len-1; j < n; i++, j++)
            {
                dp[i][j] = dp[i+1][j] + 1;//s[i]需要匹配一个括号
                path[i][j] = -1;//记录路径
                for(int k = i+1; k <= j; k++)//小序列更新大序列
                {
                    if((s[i] == '(' && s[k] == ')') || (s[i] == '[' && s[k] == ']'))
                    if(dp[i][j] > dp[i+1][k-1] + dp[k+1][j])
                    {
                        dp[i][j] = dp[i+1][k-1] + dp[k+1][j];
                        path[i][j] = k;//记录路径
                    }
                }
            }
        }
        prit(0, n-1);
        printf("\n");
    }
    return 0;
}