TopCoder SRM 686 (Div. 1) Easy. BracketSequenceDiv1

起床に失敗しました。

問題概要

()[] で構成された文字列が与えられる。正しい括弧列にするような文字の削除方法は何通りあるだろうか。

解法

区間 DP。

次のような関数を定義する。

• f(l,r):=区間 [l,r] を使って作ることのできる正しい括弧列の総数

遷移パターンは、

• s[l] と s[i] を対応させる
• s[l] を削除

の2通り。

s[l] と s[i] を対応させるパターン数は f(l+1,i-1)*f(i+1,r) 通り。s[l] を削除するパターン数は f(l+1,r) 通り。

TopCoder SRM 686 (Div. 1) Easy. BracketSequenceDiv ...

いかにも区間 DP で解けそうな問題。