Let $S(i,j)$ be the set of the shortest FBEs containing $x_i\ldots x_j$. We focus on non-trivial cases ($j-i\ge 2$).
If there is an element in $S(i,j)$ with the form $AB$ where neither $A$ nor $B$ is empty, there must exist $i\le k<j$ such that $x_i,\ldots, x_k$ belong to $A$ and $x_{k+1},\ldots,x_j$ belongs to $B$. Easy to see $T(i,j)=\min_k\{T(i,k)+T(k+1,j)\}$.
Otherwise, take an element from $S(i,j)$. Assume WLOG it has the form [$A$]. Note $x_{i+1},\ldots,x_{j-1}$ are contained in $A$, we have $T(i,j)\ge T(i+1,j-1)+2$. Furthermore, if either $x_i\neq$ [ or $x_j\neq$ ] (say $x_i\neq$ [ WLOG), then $A$[] (with the form $AB$) is also an FBE containing $x_i\ldots x_j$, which contradicts to the assumption. Hence $x_i$ and $x_j$ must match.
Combining the two paragraphs above, we have proved
- if $x_i$ and $x_j$ doesdo not match,
$$T(i,j)= \min_k\{T(i,k)+T(k+1,j)\},$$
- if $x_i$ and $x_j$ match,
$$T(i,j)\ge \min\left\{\min_k\{T(i,k)+T(k+1,j)\}, T(i+1,j-1)+2\right\}.$$
Note concentrating a shortest FBE containing $x_i\ldots x_k$ and a shortest FBE containing $x_{k+1}\ldots x_j$ constitutes an FBE containing $x_i\ldots x_j$, so $T(i,j)\le \min_k\{T(i,k)+T(k+1,j)\}$. In addition, if $x_i$ and $x_j$ match, say $x_i=$ [ and $x_j=$ ], and let $s$ be a shortest FBE containing $x_{i+1}\ldots x_{j-1}$, then [$s$] is an FBE containing $x_i\ldots x_j$, so $T(i,j)\le T(i+1,j-1)+2$. As a conclusion, if $x_i$ and $x_j$ match,
$$T(i,j)\le \min\left\{\min_k\{T(i,k)+T(k+1,j)\}, T(i+1,j-1)+2\right\}.$$
So the recursion turns out to be
- if $x_i$ and $x_j$ doesdo not match,
$$T(i,j)= \min_k\{T(i,k)+T(k+1,j)\},$$
- if $x_i$ and $x_j$ match,
$$T(i,j)= \min\left\{\min_k\{T(i,k)+T(k+1,j)\}, T(i+1,j-1)+2\right\}.$$