1183. Brackets Sequence - Timus

#include <bits/stdc++.h>
#define INF 0x3f3f3f3f

using namespace std;

const int NMAX = 128;
int dp[NMAX][NMAX];
string s, ans[NMAX][NMAX];
// dp[i][j] - numarul minim de paranteze ce trebuie adaugate secventei i...j pentru a fi corecta
// ans[i][j] - noua secventa i...j(corecta)

char reversed(char ch) {
    if(ch == '(')
        return ')';
    if(ch == ')')
        return '(';
    if(ch == '[')
        return ']';
    return '[';
}

void Solve(int i, int j) {
    if(i == j) {
        dp[i][j] = 1;
        string aux{s[i], reversed(s[i])};
        if(aux[0] == ')' || aux[0] == ']')
            swap(aux[0], aux[1]);
        ans[i][i] = aux;
    }
    else
        if(i == j - 1 && s[i] == reversed(s[j]) && (s[i] == '(' || s[i] == '[')) {
            string aux{s[i], s[j]};
            ans[i][j] = aux;
            dp[i][j] = 0;
        }
    else {
        if(s[i] == reversed(s[j]) && (s[i] == '(' || s[i] == '[')) {
            if(dp[i + 1][j - 1] == INF)
                Solve(i + 1, j - 1);
            if(dp[i][j] > dp[i + 1][j - 1]) {
                dp[i][j] = dp[i + 1][j - 1];
                ans[i][j] = s[i] + ans[i + 1][j - 1] + s[j];
            }
        }
        for(int k = i; k < j; ++k) {
            if(dp[i][k] == INF)
                Solve(i, k);
            if(dp[k + 1][j] == INF)
                Solve(k + 1, j);
            if(dp[i][j] > dp[i][k] + dp[k + 1][j]) {
                dp[i][j] = dp[i][k] + dp[k + 1][j];
                ans[i][j] = ans[i][k] + ans[k + 1][j];
            }
        }
    }
}

int main() {
    cin >> s;
    s = '0' + s;
    int N = s.size() - 1;
    for(int i = 0; i < NMAX; ++i)
        for(int j = 0; j < NMAX; ++j)
            dp[i][j] = INF;
    Solve(1, N);
    cout << ans[1][N];
}