区間DPを勉強してみた

精進してるとやっぱり出てきた区間DP...

避けてきたけど、今回は少しコツをつかもうと思って勉強してみました

What's 区間DP?

区間についての動的計画法です。はい。

....

は？

訳がわからんから取り敢えず問題解いてみよう

だるま落としぃ

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1611&lang=jp

どのようにブロックの対を取り出せばいいのか....っていうところなんですが...

まずはdpの保持する値を決めてしまいましょう

dp[l][r] := 区間[l , r)で取り除くことのできるブロックの数

どのように求めるか

２つパターンがあって、今見ている区間を[l,r)とすると

1.lのブロックとr - 1のブロックが対になれる
2.[l,mid) , [mid , r)に区間を分ける

1.が満たすのはどういう状況か...

それは

・w[l]とw[r - 1]の差が1
・[l + 1,r - 1)が完全に取り除ける
    -> dp[l + 1][r - 1] が r - l - 2 

という条件にあたりますね

[l] [......] [r]

という配置のとき

[......]

が弾き出すことができて,かつ

[l][r]

をはじき出せるかということになります

2.を考えると

//左側で取り除けた量 + 右側で取り除けた量
dp[l][r] = dp[l][mid] + dp[mid][r]

というふうに出来ます

これをDPすればできちゃいそう！

どうやって書こう

再帰で書く方法と,ボトムアップ(for文だけのやつ)で書く方法,

どちらもありますが、再帰で書いたほうがわかりやすいかも(個人差)

int rec(int l,int r){
    //既に計算済み？
    if(dp[l][r] != -1) return dp[l][r];

    //これ以上取り除けない？
    if(abs(l - r) <= 1) return 0;

    int res = 0;
    //パターン1.
    if(abs(w[l] - w[r - 1]) <= 1 && rec(l + 1,r - 1) == r - l - 2)
    {
        //[l , r)がはじき出せるので
        res = r - l;
    }

    //パターン２.区間を分ける
    for(int mid = l + 1;mid <= r - 1;mid++)
    {
        res = max(res , rec(l,mid) + rec(mid,r));
    }
    return dp[l][r] = res;
};

こんな感じ

あとはrec(0,n)で求められるね

ひゃい

ボトムアップはこんな感じです

for(int W = 2;W <= n;W++)
{
    //left
    for(int l = 0;l < n;l++)
    {
        int r = l + W;
        if(r > n) continue;

        if(dp[l + 1][r - 1] == W - 2 && abs(w[l] - w[r - 1]) <= 1)
            dp[l][r] = W;

        for(int mid = l;mid <= r;mid++)
        {
            dp[l][r] = max(dp[l][r] , dp[l][mid] + dp[mid][r]);
        }

    }

}

幅を広げていくイメージです

コツ？？

結局、遷移が大事だったね(ア)

どのように小さな区間に遷移していくかが問題っぽい...

今回は基本的なことしか書いてないからまだわからないけど

また違う問題で書こう