区間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文で配列の更新処理を行おうとすると難しいことが多いので、メモ化再帰を利用すると実装しやすくなります。

練習問題