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
- $$$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. 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))$$$
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 consist of '(' and ')' then there is a $$$O(n)$$$ solution
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
