Minimum number of charactor need to add to make a valid barrack string

#	User	Rating
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

#	User	Contrib.
1	cry	164
1	maomao90	164
3	Um_nik	163
4	atcoder_official	160
5	-is-this-fft-	158
6	adamant	157
6	awoo	157
8	TheScrasse	154
8	nor	154
10	djm03178	153

Target: Optimize $$$dp[l][r] = min(dp[l][k] + dp[k + 1][r])$$$ into $$$O(n^2\ polylog)$$$ or lower

My detailed question is below

The statement

A pair of charactor $$$(L, R)$$$ is called good or matched to each other if it satisfy one of below

$$$L =$$$ '(' and $$$R =$$$ ')'
$$$L =$$$ '[' and $$$R =$$$ ']'
$$$L =$$$ '{' and $$$R =$$$ '}'

Notice that if $$$(L, R)$$$ is good then $$$(R, L)$$$ is not good

String can have many variation of categories, one of that is good string. Let a string $$$S$$$ of size $$$N$$$ is called good if

$$$S$$$ is empty (its length $$$N = 0$$$)
$$$S = S_1 + S_2 + \dots + S_n$$$. Where $$$S_i$$$ is a good string and + symbol mean that string concaternation
$$$S = L + S_x + R$$$ where $$$S_x$$$ is a good string and $$$(L, R)$$$ is a good pair of charactor

Given a string $$$S$$$ of size $$$N$$$. We can add some charactor '(', ')', '[', ']', '{', '}' into anywhere in string $$$S$$$ but you cant replace or remove them.

The question is that: What is the minimum number of charactor need to add into string to make it good ?

The dynamic programming solution $$$O(n^3)$$$

Lets $$$F(l, r)$$$ is the answer for substring $$$S[l..r]$$$.

If $$$l > r$$$ then the string is empty, hence the answer is $$$F(l, r) = 0$$$
If $$$l = r$$$ then we should add one charactor to match $$$S_l$$$ to make this substring good, hence the answer is $$$F(l, r) = 1$$$
If $$$S_l$$$ match $$$S_r$$$, the outside is already make a pair, so $$$F(l, r) = F(l + 1, r - 1) + 0$$$
Else we can split into 2 other substring $$$S[l..r] = S[l..k] + S[k+1..r]$$$, for each $$$k$$$ we have $$$F(l, r) = F(l, k) + F(k+1, r)$$$ hence $$$F(l, r) = min(F(l, k) + F(k+1, r))$$$

Recursive Code

///   Minimum number of error
/// = Minimum number of char need to add
int f[LIM][LIM]; /// Min error in substring s[l..r]
int solve(int l = 0, int r = n - 1)
{
    if (l > r) return 0; /// empty substring
    if (l == r) return 1; /// dont pair with other

    int &res = f[l][r];
    if (res != +INF) return res; /// calculated

    if (match(s[l], s[r])) /// paired up, no error
    {
        res = 0 + solve(l + 1, r - 1);
    }
        
    /// Split string into 2 halves
    /// s[l..r] = s[l..k] + s[k+1..r]
    /// f[l..r] = min(f[l..k] + f[k+1..r])
    for (int k = l; k < r; ++k)
    {
        minimize(res, solve(l, k) + solve(k + 1, r));
    }

   return res;
}

Iterative Code

///   Minimum number of error
/// = Minimum number of char need to add
int f[LIM][LIM]; /// Min error in substring s[l..r]
int solve()
{
    memset(f, 0, sizeof(f));
    for (int r = 0; r < n; ++r)
    {
        for (int l = r; l >= 0; --l)
        {
            f[l][r] = r - l + 1; /// Add one charactor to each one
            if (match(s[l], s[r])) /// Outside make a good pair of string
            {
                f[l][r] = f[l+1][r-1];
            }

            /// Split string into 2 halves
            /// s[l..r] = s[l..k] + s[k+1..r]
            /// f[l..r] = min(f[l..k] + f[k+1..r])
            for (int k = l; k < r; ++k)
            {
                minimize(f[l][r], f[l][k] + f[k+1][r]);
            }
        }
    }

    return f[0][n - 1];
}

Full Code

#include <iostream>
#include <cstring>
#include <cstdio>

using namespace std;

template<typename T> void maximize(T &res, const T &val) { if (res < val) res = val; }
template<typename T> void minimize(T &res, const T &val) { if (res > val) res = val; }
void file(const string FILE = "Test")
{
    freopen((FILE + ".INP").c_str(), "r", stdin);
    freopen((FILE + ".OUT").c_str(), "w", stdout);
}

const int LIM = 1010;
const int INF = 0x3f3f3f3f;
/// ====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====

int n;
string s;

///// One variation
//int solve()
//{
//    int res = 0, diff = 0;
//    for (char c : s)
//    {
//        diff += (c == '(') ? +1 : -1;
//        if (diff < 0)
//        {
//            diff = 0;
//            ++res;
//        }
//    }
//    res += diff;
//
//    return res;
//}

bool match(char l, char r)
{
    return (l == '(' && r == ')')
        || (l == '[' && r == ']')
        || (l == '{' && r == '}');
}

///   Minimum number of error
/// = Minimum number of char need to add
int f[LIM][LIM]; /// Min error in substring s[l..r]

/// Iterative
int solve()
{
    memset(f, 0, sizeof(f));
    for (int r = 0; r < n; ++r)
    {
        for (int l = r; l >= 0; --l)
        {
            f[l][r] = r - l + 1; /// Add one charactor to each one
            if (match(s[l], s[r])) /// Outside make a good pair of string
            {
                f[l][r] = f[l+1][r-1];
            }

            /// Split string into 2 halves
            /// s[l..r] = s[l..k] + s[k+1..r]
            /// f[l..r] = min(f[l..k] + f[k+1..r])
            for (int k = l; k < r; ++k)
            {
                minimize(f[l][r], f[l][k] + f[k+1][r]);
            }
        }
    }

    return f[0][n - 1];
}

/// Recursive
//int solve(int l = 0, int r = n - 1)
//{
//    if (l > r) return 0; /// empty substring
//    if (l == r) return 1; /// dont pair with other
//
//    int &res = f[l][r];
//    if (res != +INF) return res; /// calculated
//
//    if (match(s[l], s[r])) /// paired up, no error
//    {
//        res = 0 + solve(l + 1, r - 1);
//    }
//
//     /// Split string into 2 halves
//     /// s[l..r] = s[l..k] + s[k+1..r]
//     /// f[l..r] = min(f[l..k] + f[k+1..r])
//     for (int k = l; k < r; ++k)
//     {
//         minimize(res, solve(l, k) + solve(k + 1, r));
//     }

//    return res;
// }


int main()
{
    file();
    cin >> s;
    n = s.size();

    memset(f, +INF, sizeof(f));
    cout << solve();
    return 0;
}

Complexity:

$$$F(l, r)$$$ have $$$O(n^2)$$$ states
In each substring $$$S[l..r]$$$, we maybe to have a for-loop $$$O(n)$$$
Hence the upper bound of the complexity is $$$O(n^3)$$$

My question

If the string $$$S$$$ is only consist of '(' and ')' then there is a Linear ($$$O(n)$$$) solution

The solution

/// res: number of barrack need to be added
/// diff: difference between number of '(' - ')', diff can be negative
int solve()
{
    int res = 0, diff = 0;
    for (char c : s) /// for each charactor
    {
        diff += (c == '(') ? +1 : -1;
        if (diff < 0) /// Add a '(' here, since there are more ')' then '('
        {
            diff = 0; /// After adding a '(', diff = 0 <=> equal '(' and ')'
            ++res;
        }
    }
    res += diff; /// Add (diff) close barrack at the end

    return res;
}

Can my algorithm ($$$dp[l][r] = min(dp[l][k] + dp[k + 1][r])$$$) improved into $$$O(n^2\ polylog)$$$ or lower in somehow ?
Failed to use Knuth algorithm $$$(dp[l][r] = min(dp[l][k] + dp[k][r] + cost[l][r])$$$ since fully-motone condition is not satisfied

Rev.	By	When	Δ	Comment
en14	SPyofgame	2021-02-05 13:56:41	7556
en13	SPyofgame	2021-02-04 10:55:27	273
en12	SPyofgame	2021-02-04 10:53:42	256
en11	SPyofgame	2021-02-04 10:02:38	5508
en10	SPyofgame	2021-02-04 09:43:38	97
en9	SPyofgame	2021-02-04 08:02:15	303
en8	SPyofgame	2021-02-04 07:39:33	58
en7	SPyofgame	2021-02-04 07:18:50	2
en6	SPyofgame	2021-02-04 07:18:24	183
en5	SPyofgame	2021-02-04 07:13:19	192
en4	SPyofgame	2021-02-04 06:10:26	1008
en3	SPyofgame	2021-02-04 05:56:52	3217
en2	SPyofgame	2021-02-04 05:10:01	76
en1	SPyofgame	2021-02-04 05:08:52	3831	Initial revision (published)

The statement

The dynamic programming solution $$$O(n^3)$$$

My question

History