解説
この問題は動的計画法 (DP) を用いて解くことが出来ます。
部分列の条件に従い、以下のように状態遷移を考えることが出来ます。
状態を以下のように定義します:
dp[i][j]: i番目までの文字で、部分列が状態jとなるものの個数
部分列の状態jを以下のように定義します:
- 0: まだ何もできていない
- 1:
(までできた - 2:
(^までできた - 3:
(^^までできた - 4:
(^^)完成
次に、状態遷移を考えます:
- 文字が
(の場合、状態0から状態1へ遷移する - 文字が
^の場合、状態1から状態2へ、そして状態2から状態3へ遷移する - 文字が
)の場合、状態3から状態4へ遷移する
状態jの数を更新する際、前の状態の数を継承することも忘れてはいけません。これにより、状態0から状態3までの数は次の文字に対しても適用されます。