I am currently working on the following problem that involves developing a dynamic programming algorithm for finding the length of the shortest fully bracketed expression (FBE), $y$ that contains a given string $x = x_1x_2...x_n$. An FBE is defined as a string over the characters (,),[, and ] that is either
- the empty string
- the string $[T]$ or $(T)$, where $T$ is a fully bracketed expression, or
- the string $TU$, where $T$ and $U$ are fully bracketed expressions.
So far I have worked through the potential recursive function $T(i,j)$ which I've defined as the length of the shortest possible FBE that contains $x_i...x_j$ as a subsequence (not necessarily a string). And I know that in the shortest FBE containing $x_i...x_j$ that $x_i$ is either "mathced" to an appropriate character $x_k$ such that $i + 1 \leq k \leq j$, or it isn't. So I think that I need two cases; either the former is true, or the latter is true.
I'm having trouble formalizing this and creating a recursion. I'm not sure how to deal with the addition of characters. Any help would be appreciated! Thanks!