Brackets

题目描述

We give the following inductive definition of a “regular brackets” sequence:

• the empty sequence is a regular brackets sequence,
• if s is a regular brackets sequence, then (s) and [s] are regular brackets sequences,
• if a and b are regular brackets sequences, then ab is a regular brackets sequence,
• no other sequence is a regular brackets sequence.

For instance, all of the following character sequences are regular brackets sequences:
(), [], (()), ()[], ()[()],
while the following character sequences are not:
(, ], )(, ([)], ([(].
Given a brackets sequence of characters $a_1a_2 \ldots a_n$, your goal is to find the length of the longest regular brackets sequence that is a subsequence of $s$. That is, you wish to find the largest $m$ such that for indices $i_1, i_2, \ldots, i_m$ where $1 \le i_1 \lt i_2 \lt \cdots \lt i_m \le n$, $a_{i_1}a_{i_2} \ldots a_{i_m}$ is a regular brackets sequence.
Given the initial sequence ([([]])], the longest regular brackets subsequence is [([])].

算法分析

$$f_{i, j}= \begin{cases} \max(f_{i + 1, j – 1} + 2, f_{i, k} + f_{k + 1, j} \mid i \le k \lt j), & a_i \text{ matches } a_j \\ \max(f_{i, k} + f_{k + 1, j} \mid i \le k \lt j), & \text{otherwise} \end{cases}$$

418 I'm a teapot