Typical DP Contest - I イウィ

I: イウィ - Typical DP Contest | AtCoder

//
// iwiwii -> iwi ->
// ~~   ~    ~~~
// 残りが連結されることを考慮しないとダメ
//
// 区間に対する DP でやる
//
// ある区間 [l,r) の削除数がわかったとして、
//
// wiwiwi -> wwi
//        -> wiw
//
// のように削除される iwi の数が同じ場合これらの違いはどうやって吸収するのか？
//
//  * 削除する区間の始点をかえることで吸収できる。
//  * その区間の全ての文字が削除されたかは削除された文字数から判定できる
//
class i_iwi {
public:
    void solve(void) {
        string S;
        cin>>S;
        int N = S.length();

        // dp[l][r] := 区間 [l,r) から iwi を取り除くときに、のぞかれる文字数の最大数
        vector<vector<int>> dp(N+1, vector<int>(N+1,0));

        // [l,r) 区間の全ての文字が削除されたか
        auto all_removed = [&](int l, int r)->bool {
            return (dp[l][r] == r-l);
        };

        for (int w = 1; w <= N; ++w) // 区間の幅
        for (int l = 0; l+w <= N; ++l)  // 区間の開始点
        {
            int r = l+w;
            dp[l][r] = dp[l+1][r]; // 幅 w-1 のときの結果を引き継ぐ
            // dp[l][r] = dp[l][r-1];

            // 区間を二分割して(幅を w より小さくする)それぞれで dp 結果を参照する。
            // 区間をまたぐような操作は別の区間の分割に含まれるはず
            for (int k = l+1; k < r; ++k)
                dp[l][r] = max(dp[l][r], dp[l][k]+dp[k][r]);
            // 区間が ixxx...xxxi になっているケース
            if (S[l] == 'i' && S[r-1] == 'i')
            {
                // x 毎にみていく
                for (int k = l+1; k < r-1; ++k)
                {
                    if (S[k] == 'w' && all_removed(l+1,k) && all_removed(k+1, r-1))
                        dp[l][r] = r-l; // 全ての文字が削除された
                }
            }
        }
        cout<< dp[0][N]/3 <<endl; // dp[i][j] は削除された文字数で３文字づつ削除されるので
    }
};