SRM686 Div1 Easy "BracketSequenceDiv1"
解法
区間dpる。
dp[L][R] := LからRまでの区間にて、シーケンスをcorrectにする消し方の場合の数
初期化
L == Rの場合、その一文字を消すしかcorrectにする方法はないので1
更新
Rのカッコに着目し、こいつを追加したときにどうやって更新するか考える。
まず、Rのカッコが"("や"["だった場合、これは消すしかcorrectにする方法がないので消すことにする。
すると、dp[L][R] = dp[L][R - 1]となる。
Rのカッコが")"や"]"だった場合、まず消す場合は同様にdp[L][R - 1]パターンでcorrectにできる。
それから、LからR - 1の間の"("か"["のカッコとペアを作ることが出来るため、消さないで残す方法があることになる。
ペアとするカッコのインデックスをiとすると、Lからi - 1, i + 1からR - 1それぞれでパターンを作ることができるので、それらを掛け合わせたdp[L][i - 1] * dp[i + 1][R - 1]だけcorrectにできる。
下図を見て欲しい。
図は、Rのカッコをindex4のカッコとペアにするぞ!!と意気込んでいる状態である。
すると、黄色の部分と緑の部分がそれぞれ独立してパターンを作ることができるので、dp[1][3] * dp[5][6]がdp[1][7]に足しこまれるという感じ。
ペアとするカッコはLからR - 1までを走査して、どんどん足しこんでく。
結果
dp[0][n - 1] - 1
※全部消すのはNGだ!
事後
Editorialのソースコードの簡潔さよ・・・
ソースコード
long long dp[45][45]; class BracketSequenceDiv1 { public: long long count(string s) { int n = s.size(); for (int len = 1; len <= n; len++) { for (int L = 0; L <= n - len; L++) { int R = L + len - 1; if (len == 1) { // 長さ1のところは消すの1パターン dp[L][R] = 1; } else { if (s[R] == '(' || s[R] == '[') { // 消すしかない! dp[L][R] = dp[L][R - 1]; } else { // 消す! dp[L][R] = dp[L][R - 1]; // ペアを順に探していく char pair = s[R] == ')' ? '(' : '['; for (int i = L; i < R; i++) { if (s[i] == pair) { // 1つ目のサブセット int L1 = i + 1; int R1 = R - 1; long long sub1 = L1 <= R1 ? dp[L1][R1] : 1; // 2つ目のサブセット int L2 = L; int R2 = i - 1; long long sub2 = L2 <= R2 ? dp[L2][R2] : 1; dp[L][R] += sub1 * sub2; } } } } } } return dp[0][n - 1] - 1; } };