SRM 686 div1 easy: BracketSequenceDiv1(その 2)

さっきの問題の dp 解です。
mayokoex.hatenablog.com

dp[l][r] = [l, r) の区間における, valid な括弧列の数, とします。

valid な括弧列の生成の仕方は,

• l 番目を無視する(区間 [l+1, r) )
• l 番目と i 番目が一致する時, [l+1, i) と [i+1, r) に分けて考える

の 2 通りがあるので, 両方を考えて和を取れば良いです。

こっちのほうが実装が 100 倍楽ですね。

ll dp[55][55];
string s;

// [l, r)
ll dfs(int l, int r) {
    ll& ret = dp[l][r];
    if (ret >= 0) return ret;
    if (l==r) return ret = 1;
    ret = dfs(l+1, r);
    for (int i = l+1; i < r; i++) {
        if ((s[l] == '(' && s[i] == ')') || (s[l] == '[' && s[i] == ']')) {
            ret += dfs(l+1, i) * dfs(i+1, r);
        }
    }
    return ret;
}

class BracketSequenceDiv1 {
public:
    long long count(string s) {
        ::s = s;
        memset(dp, -1, sizeof(dp));
        return dfs(0, s.size()) - 1;
    }
};