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
Main statement
Given a string with 3 types of barracks '()', '[]', '{}'. Calculate minimum number of charactor need to add into string that make it a valid parentheses string.
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 ?
Limitation: $$$N = |S| \leq 500$$$
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$$$
- 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))$$$
- Notice that when $$$S_l$$$ match $$$S_r$$$, $$$F(l, r) = min(F(l + 1, r - 1), 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)$$$
The other dynamic programming solution $$$O(n^3)$$$
Base cases:
- If $$$l > r$$$ then the string is empty, hence $$$F(l, r) = 0$$$
- If $$$l = r$$$ then we should add one charactor to match $$$S_l$$$ to make this substring good, hence $$$F(l, r) = 1$$$
Branch and bound cases:
- If $$$S_l$$$ is close barrack, then add a open barrack before it, hence $$$F(l, r) = F(l + 1, r) + 1$$$
- If $$$S_r$$$ is open barrack, then add a close barrack after it, hence $$$F(l, r) = F(l, r - 1) + 1$$$
- If $$$(S_l, S_{l+1})$$$ is good, then just paired it up, hence $$$F(l, r) = F(l + 2, r) + 0$$$
- If $$$(S_{r-1}, S_r)$$$ is good, then just paired it up, hence $$$F(l, r) = F(l, r - 2) + 0$$$
Main cases:
For each $$$k = l \rightarrow r - 1$$$
- If $$$S_k$$$ match $$$S_r$$$, minimize $$$F(l, r)$$$ with $$$F(l, k - 1) + 0 + F(k + 1, r - 1)$$$
- Else add a open charactor at k to match $$$S_r$$$, minimize $$$F(l, r)$$$ with $$$F(l, k) + 1 + F(k + 1, r - 1)$$$
Complexity:
- $$$F(l, r)$$$ have $$$O(n^2)$$$ states
- In each substring $$$S[l..r]$$$, we maybe to have a for-loop $$$O(n)$$$ or $$$O(1)$$$ for transistion
- Hence the upper bound complexity is $$$O(n^3)$$$
- Hence the lower bound complexity is $$$O(n^2)$$$
My question
- If the string $$$S$$$ is only consist of '(' and ')' then there is a Linear ($$$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
