区間DP の考え方と使える状況まとめ

2020年3月10日動的計画法DP,テーマ記事,競プロ,区間,区間DP,区間の除去・圧縮・合体

競技プログラミングで良く使われる動的計画法の1種、「区間DP」と呼ばれるものについてまとめました。

区間DPとは

区間DPとは、区間を表す添え字を持つ動的計画法(DP)のことです。

基本的には、以下のような DPを考えます。

\(dp[ l ][ r ]\) := 区間 [ l, r ) について、最適な状況下での何かしらの値

漸化式の更新方法は問題ごとに異なりますが、

  • 区間 [ l, r ) を更新する際に、[ l+1, r ) と [ l, r-1 ) などの左右から1つ増減させたものを確認する
  • 区間 [ l, r ) を更新する際に、[ l, i ) と [ i, r ) を全ての i について確認する

の2種類が多くある印象です。もう少し dp 更新の漸化式っぽくすると

  • dp[ l ][ r ] = dp[ l+1 ][ r ] と dp[ l ][ r-1 ] から更新（左端か右端の1つが変化する）
  • dp[ l ][ r ] = 全ての i について dp[ l ][ i ] と dp[ i ][ r ] を確認して更新（2つの区間を組み合わせて新しいものを得る）

という形になります。

よくある適用可能な状況

プログラミングコンテストなどで、区間DPが良く使われそうなシチュエーションは以下のようなものがあります。

区間の除去・圧縮・合体などが生じる時

ある区間 [l, r) について、最適に除去・圧縮・合体した時の値を dp[ l ][ r ] などと保持する場合が多いです。

実際にシミュレーションしようとして、配列から要素を削除したりするのは難しいです。この場合は区間DPが強力な手段として使えます。

\(O(N^2)\) が間に合いそうなとき（\(N \leq 3000\) 前後）

一回の更新が定数時間でできる場合、このような制約になることがあります。

  • dp[ l ][ r ] = dp[ l+1 ][ r ] と dp[ l ][ r-1 ] から更新

という状況が多い印象です。\(O(N^2)\) 程度の計算量になります。

\(O(N^3)\) が間に合いそうなとき（\(N \leq 500\) 前後）

一回の更新が N に比例した回数でできる場合、このような制約になることがあります。

  • dp[ l ][ r ] = 全ての i について dp[ l ][ i ] と dp[ i ][ r ] を確認して更新

という状況が多いです。\(O(N^3)\) 程度の計算量になります。

例題

AOJ Daruma Otoshi を例題として解いてみましょう。

問題概要

長さ n の数列 \(\{w_1, w_2, w_3, \cdots, w_n\}\) が与えられ、以下の操作を好きなだけ行える。

  • 数列の中から隣り合うペアを1つ選び、差が 1 以内になるなら除去する

最大でいくつ取り除くことができるか求めよ。

制約

  • \(1 \leq n \leq 300\)
  • \(1 \leq w_i \leq 1000\)

考え方

問題設定から、区間DPの典型的な状況であると分かります。「区間の除去」という操作ですし、制約からいっても \(O(n^3)\) 程度なら計算が間に合いそうです。

区間DPのテンプレートに沿って、以下のようなDPを考えてみましょう。

\(dp[ l ][ r ]\) := 区間 [ l, r ) について、取り除くことができる数の最大値

更新は、2通りの場合を考えればよいです。

  1. \(w_l, w_{r-1}\) が一緒に取り除かれる時：区間 [l+1, r-1) は全て取り除け、更に \(w_l, w_{r-1}\) の差が 1以下の時のみ生じる
  2. 1. 以外の時：区間 [ l, i ) と 区間 [ i, r) に分けて考える

1つ目の方は、区間 [ l, r ) が全て取り除かれるので、全体で r-l 個取り除けることになります。

2つ目の方はほぼテンプレート通りで、区間 [ l, i ) と 区間 [ i, r) での値を組み合わせれば良く、

  • \(dp[ l ][ r ] = \max(dp[ l ][ i ] + dp[ i ][ r ])\)

のようになります。

C++での実装例

区間DPは、for文で配列の更新処理を行おうとすると難しいことが多いので、メモ化再帰を利用すると実装しやすくなりおすすめです。

ループを用いてDPの更新を行う場合は、更新（緩和）の順番が難しくなりがちですが、そちらのほうが分かりやすい人はそちらで実装してみると良いでしょう。

#include <bits/stdc++.h>
#define ALL(obj) begin(obj), end(obj)
using namespace std;

template <class T>
bool chmax(T &a, const T &b) {
    if (a < b) {
        a = b;
        return 1;
    }
    return 0;
}

int N;
vector<int> w;
vector<vector<int>> dp;

int rec(int l = 0, int r = N) { // メモ化再帰
    if ((r - l) <= 1) return 0;
    if ((r - l) == 2) {
        if (abs(w[l] - w[l + 1]) <= 1) {  // 隣り合う2つの差が1以下
            return 2;
        } else {
            return 0;
        }
    }

    int &ret = dp[l][r]; // 更新の対象についての参照を宣言
    if (ret != -1) return ret;  // 既に計算済みならその値を使う

    // 1. 全部取り除けるとき
    if (abs(w[l] - w[r-1]) <= 1 && rec(l + 1, r - 1) == r - l - 2) chmax(ret, r - l);
    // 2. そうでない時
    for (int i = l + 1; i <= r - 1; i++) {
        chmax(ret, rec(l, i) + rec(i, r));
    }

    return ret;
}

int main() {
    vector<int> ans;
    while (true) {
        cin >> N;
        if (N == 0) break;
        w.resize(N);
        for (int i = 0; i < N; i++) {
            cin >> w.at(i);
        }

        dp.assign(N + 2, vector<int>(N + 2, -1));  // 初期化

        ans.push_back(rec());
    }

    for (auto i : ans) {
        cout << i << endl;
    }

    return 0;
}

練習問題

動的計画法DP,テーマ記事,競プロ,区間,区間DP,区間の除去・圧縮・合体