動的計画法

概要

再帰的な問題を高速に解くアルゴリズム。
つまり「少し小さい問題の答えがわかっていれば簡単」というタイプの問題を解く方法。

英語での呼び方 Dynamic Programming の頭文字を取って DP と呼ばれることも多い。

ABCでは主にD問題以降で登場する。
ただし、応用の幅が広く、内容によってはE・F問題級やそれ以上に難しい問題も多い。

アルゴリズム内容

動的計画法を用いる有名問題の例として、部分和問題を考える。

5 9 7 2 4 のうちいくつかを選んで、合計を15にすることができるか？

この場合、最後の 4 を使わないなら、前の $4$ 個で合計 $15$ を作れればよい。
最後の 4 を使うなら、前の $4$ 個で合計 $11$ を作れればよい。
つまり、この問題は

5 9 7 2 のうちいくつかを選んで、合計を11または15にすることができるか？

の答えがわかっていれば、すぐに答えられる。
数列の長さが $1$ つ少ない問題の答えを調べてあれば、元の問題は簡単に解けることになる。

では、

5 9 7 2 のうちいくつかを選んで、合計を11にすることができるか？

は、どう解くか。
同じように、

5 9 7 のうちいくつかを選んで、合計を9または11にすることができるか？

を解けばよい。

結局、数字が $1$ つもない状態という明らかにすぐ解ける問題から始めることになる。
その結果を継承しながら少しずつ大きな問題に答えていくことで、元の問題も解ける。
具体的には、次の表を上から順に埋めていけばよい。

例えば、色を付けた各マスは次のように決まる。

• 黄色で示した 5, 9 の行の $13$ 列目では、5 だけで合計 $4$ も $13$ も作れないため × となる。
• 緑色で示した 5, 9, 7 の行の $1$ 列目では、5, 9 で合計 $1$ を作れないため × となる。
• 青色で示した 5, 9, 7, 2 の行の $11$ 列目では、5, 9, 7 で合計 $9$ を作れるため ○ となる。
• 赤色で示した 5, 9, 7, 2, 4 の行の $7$ 列目では、5, 9, 7, 2 で合計 $7$ を作れるため ○ となる。

$2$ 番目の例では、$1<7$ なので、合計 $-6$ を作れるかどうかは調べていない。
最終的に、元の問題には表の右下を見て答えればよい。

この部分和問題では、vector<bool> で「合計が $i$ であるような選び方ができるか」を表している。
そして、そのデータを継承しながら、数列の要素を $1$ つずつ増やしていった。

問題によっては整数 $1$ つだけを継承したり、vector<int> を継承したり、文字列を継承したりする。
増やしていく内容も、数列を長くしていく以外にさまざまあり、$2$ 方向に増やしていくこともある。
見るのも $1$ 段上だけではなく、$2$ 段上を見たり、それまでの状態を全て見たりする。
「何をどう増やしていくのか」「継承するデータは何か」の選び方が、問題によって幅広く変わってくる。

DPまとめコンテストにはある程度パターンがそろっているので、有名なパターンには慣れておきたい。

コード例

上の部分和問題だと、数列の長さを $n$、要求される合計値を $s$ として、このようになる。

vector dp(n+1,vector<bool>(s+1,false));
dp.at(0).at(0) = true;
for (int i=1; i<=n; i++) {
  for (int j=0; j<=s; j++) {
    if (dp.at(i-1).at(j)) dp.at(i).at(j) = true;
    if (j>=a.at(i-1)&&dp.at(i-1).at(j-a.at(i-1))) dp.at(i).at(j) = true;
  }
}

$1$ 行目は、DPテーブルの用意。
$0$ のときから $n$ や $s$ ちょうどのときまで調べたいので、サイズが縦 $n+1$ で横 $s+1$ にする必要がある。

$2$ 行目は、最も簡単に解けるところの仕込み。
前掲の表の最上段を全て埋めている。（false 初期化を活用してコード上は $1$ ヶ所しか変更していないが）

$3$ 行目以降は、$2$ 行目で埋めたところ以外のデータ作成。
前述の規則で、$2$ 重ループで埋めている。
（bool 型の処理を工夫すればもっと高速化できるが、ここではわかりやすさを優先した）

問題によって表の作り方は全く違うものになってくるので、都度しっかり考える必要がある。
考えるべき内容は、主に以下。

• dp[i][j] などの各状態が何を表すか
• 最初から答えがわかる初期状態はどこにあるか
• どの状態を参照して更新するか
• 参照元が計算済みになる処理順
• 最終的な答えがどの状態に入るか
• 状態数と遷移数から求めた計算量

使い方の応用

もらうDPと配るDP

DPテーブルのある位置 $A$ から $B$ にデータを反映させるやり方は、実は $2$ 種類ある。

• ループが $A$ を見るときにこの反映を実行する（配るDP）
• ループが $B$ を見るときにこの反映を実行する（もらうDP）

簡単な問題にはもらうDPの方が考えやすい問題が多いため、最初はそちらから練習するとよい。
難しい問題になると配るDPの方がいい問題も出てくるので、最終的には両方できる必要があるが。

上の部分和問題のコード（もらうDP）を、配るDPで書くと以下のようになる。

vector dp(n+1,vector<bool>(s+1,false));
dp.at(0).at(0) = true;
for (int i=0; i<n; i++) {
  for (int j=0; j<=s; j++) {
    if (!dp.at(i).at(j)) continue;
    dp.at(i+1).at(j) = true;
    if (j<=s-a.at(i)) dp.at(i+1).at(j+a.at(i)) = true;
  }
}

解の復元

上の部分和問題では、表の右下を見て "Yes" か "No" かを答えればよいとした。
しかし、問題によっては実際に和を作れるように数列の要素を選べという問題のこともある。

その場合、バックトレースをすればよい。
最初に、右下のマスからスタートする。
右下のマスが○であるということは、参照した $2$ ヶ所のデータのどちらかに○があったはずである。
両方を調べて、○である方に移動する。
移動元と移動先の関係で、その数を和に入れたかどうかがわかるはずである。
これを左上の○にたどり着くまで繰り返せばよい。

上の部分和問題の場合は、以下のように辿ることで、$9$ と $2$ と $4$ を採用すべきだとわかる。

インラインDP

DPテーブルを二次元配列ではなく一次元配列で持つ方法がある。
例えば、上の部分和問題のコードは以下のように書ける。

vector<bool> dp(s+1,false);
dp.at(0) = true;
for (int i=1; i<=n; i++) {
  for (int j=s; j>=a.at(i-1); j--) {
    if (dp.at(j-a.at(i-1))) dp.at(j) = true;
  }
}

毎回新しいデータ領域を使わずに、同じ場所を上書きで使いまわしている。
メモリが大幅に節約できるテクニックで、「インプレース更新」と呼ばれる。

さらに今回は、元々入っていたデータをそのまま活かすことで、コピーの計算時間の削減もしている。
このように無更新を活かして高速化した動的計画法は「インラインDP」と呼ばれる。
（インプレース更新は広く使われる用語だが、インラインDPはそこまで一般的ではないらしい）

しかし、更新順に注意が必要、バグの調査がしにくい、バックトレースが困難など、注意点も多い。
（$j$ を昇順にすると、同じ数を複数回使用してしまうことになる）
とはいえ、難しい問題になってくると、インラインにしないと計算量が間に合わない問題も出てくる。

bitDP

bit全探索の考えを動的計画法に組み込んだもの。
$N$ 個の要素の順序を考えたり、$N$ 個の条件を全て満たす方法を求めたりする際に用いられることが多い。
一般には、$N$ が最大 $20$ 程度の問題で使われる。
詳しくは「bitDP」の記事参照。

区間DP

各データに対する動的計画法ではなく、各区間を状態として動的計画法を行うもの。
区間の左端や右端を選んで操作するような問題で用いられることが多い。
詳しくは「区間DP」の記事参照。

桁DP

巨大な整数を上の桁から順に決めていく動的計画法。
ある数以下の整数のうち、何かの条件を満たすものの個数や総和などを求める際に用いられることが多い。
詳しくは「桁DP」の記事参照。

木DP

木の各頂点に状態を持ち、子の情報をまとめて親の状態を計算する動的計画法。
詳しくは「木DP」の記事参照。

全方位木DP

木の全ての頂点をそれぞれ根とした場合の答えを、計算結果を使い回しながら求める動的計画法。
子から親へ情報を集めた後、親側の情報も子へ渡すことで、全頂点に対する答えを効率よく求める。
詳しくは「全方位木DP」の記事参照。

DAG上のDP

DAGの各頂点に状態を持ち、辺に沿って遷移する動的計画法。
トポロジカル順に処理することで、参照元の状態を計算済みにできる。
経路数や最長経路を求める問題などで用いられる。
詳しくは「DAG上のDP」の記事参照。

注意点

表のサイズに注意

動的計画法でデータを書き込む表の大きさには限界がある。
各マスを $O(1)$ で処理する場合でも、要素数が $10^8$ 程度になると、実行時間やメモリ制限が厳しい。
そのため、実装前に「表の要素数がいくつになり、各要素の計算にどれだけかかるか」を必ず確認する。

さらに、同じ問題でも、各数値の制約に合わせて全く異なる方法で解かなくてはいけない場合がある。

例えば、ナップサック問題を考える。
ざっくりいうと、次のような問題である。

N 個の荷物がある。
i 番目の荷物は重さが w[i]、価値が v[i] である。
重さの合計が W を超えないように、いくつかの荷物を選ぶ。
価値の合計 V の最大値を求めよ。

それぞれの値が long long 型に収まるとしても、追加の制約によって解き方が大きく変わる。

（※1）重さの設定がなく、価値自体が基準を超えてはいけないという条件。

動的計画法ですらない解法も多い。
「今回のこの制約では動的計画法を使うのか」というところから判断しにくい。
それが、このアルゴリズムの真の難しさである。

関連アルゴリズム

メモ化再帰

役に立つ場面は動的計画法とほぼ同じ。
再帰的な問題をボトムアップで解くのが動的計画法、トップダウンで解くのがメモ化再帰である。
動的計画法で解ける問題はメモ化再帰でも解けることが多く、逆もまた同様である。

bitDP

bit全探索の考えを動的計画法に組み込んだもの。
$N$ 個の要素の順序を考えたり、$N$ 個の条件を全て満たす方法を求めたりする際に用いられることが多い。
一般には、$N$ が最大 $20$ 程度の問題で使われる。

区間DP

各データに対する動的計画法ではなく、各区間を状態として動的計画法を行うもの。
区間の左端や右端を選んで操作するような問題で用いられることが多い。

桁DP

巨大な整数を上の桁から順に決めていく動的計画法。
ある数以下の整数のうち、何かの条件を満たすものの個数や総和などを求める際に用いられることが多い。

木DP

木の各頂点に状態を持ち、子の情報をまとめて親の状態を計算する動的計画法。

全方位木DP

木の全ての頂点をそれぞれ根とした場合の答えを、計算結果を使い回しながら求める動的計画法。
子から親へ情報を集めた後、親側の情報も子へ渡すことで、全頂点に対する答えを効率よく求める。

DAG上のDP

DAGの各頂点に状態を持ち、辺に沿って遷移する動的計画法。
トポロジカル順に処理することで、参照元の状態を計算済みにできる。
経路数や最長経路を求める問題などで用いられる。

バックトレース

終了状態から逆再生しながら何かを調べるアルゴリズム。
動的計画法の後で、具体的な選び方や操作列などの詳細な情報を得るために用いられる。

最長増加部分列

数列の一部を、順序を保ったまま連続でなくてもよいので選び、単調増加列を作る。
その長さを最大化する問題であり、動的計画法の応用で解ける。

最長共通部分列

$2$ つの数列または文字列の一部を、順序を保ったまま連続でなくてもよいので選び、全く同じ列を作る。
その長さを最大化する問題であり、動的計画法の応用で解ける。