一般的な DP / DP の初歩
DP って何？って方向け
DPとは？
Dynamic Programming の略で、動的計画法と訳す。じゃあ Dynamic Planning ではないのか
大元は大規模な問題を小さく分割して解くことであり、競プロにおける「再帰か配列」という形は競プロ特有のものである。
競技プログラミングにおける DP
例えば、以下のような問題を考えてみよう。
商品が$ N種類ある。$ i種類目の商品は重さ$ w、価値$ vである。
各商品は$ 1個ずつあり、あなたは重さの合計が$ Wを超えない限り商品を幾つでも持てる。
持てる商品の組み合わせ全てについて、価値の合計を求めると、最大で幾つになるだろうか？
$ \Omicron(2^N)で解く方法としては bit 全探索をすれば良いが、$ N \leq 100などの制約では解けない。
これをより高速に解く方法が DP である。
DP 問題の進め方
1. 求められている答えを整理する
2. 考察
3. 必要な情報を列挙して添字に対応させる
4. 必要に応じて高速化する
1. 求められている答えを整理する
欲しい答えは「価値の合計」の最大である。ただし、重みに制限があることに注意。
2. 考察
例えば、大きな問題「$ N種類の商品を取捨選択して価値の合計が$ kになるか？」を小さく分割すると、
$ N-1種類の商品を取捨選択して価値の合計が$ k_1になるか？
$ N-2種類の商品を取捨選択して……
$ \vdots
$ 1種類の商品を取捨選択して価値の合計が$ k_{N-1}になるか？
というように分割できて、
また
$ 1種類目の商品を選択して価値の合計が$ k_{N-1}となる
ならば
$ 2種類目の商品を選べば価値の合計は$ k_{N-1} + v_2となり得る
$ 2種類目の商品を選ばなければ価値の合計は$ k_{N-1}となり得る
ことがわかる。
なお、価値の合計が変わらない方は$ v_2の商品を選ばない場合である。
ここで、$ k_{N-1} = v_1である。
従って、重みを考えずに立式すれば
$ i+1 番目の商品を選ぶとき $ \mathrm{DP} [i+1][k+v_{i+1}] = \mathrm{True}\ \text{if}\ \mathrm{DP} [i][v] = \mathrm{True}
選ばないとき$ \mathrm{DP} [i+1][k] = \mathrm{True}\ \text{if}\ \mathrm{DP} [i][v] = \mathrm{True} となる。
この時、添字が持つ情報は
$ i は、今選んでいる商品が何番目か？であり、
$ kは、現在の価値の総和がいくつか？である。
3. 必要な情報を列挙して添字に対応させる
今回は重みの情報があるので、上のようにはいかないが、ほぼ同様になる。
重みが$ W以下、を以下のように分解しよう。
重みが$ jに等しい。ただし$ 0 \leq j \leq Wを満たす。
これを踏まえて以下のように考える。
$ \mathrm{DP}[i][j] = i 番目の要素まで取捨選択していて、重みの合計が$ jであるときの価値の最大値
すると以下のように立式できる。
$ \mathrm{DP}[i + 1][j + w_i] = \mathrm{max}(\mathrm{DP}[i][j], DP[i+1][j+w_i])
$ \mathrm{DP}[i + 1][j] = \mathrm{max}(\mathrm{DP}[i][j], DP[i+1][j])
ちなみに、これを漸化式という。
なお、まず自明なこととして$ 0番目の要素まで取捨選択していて、重みの合計が$ 0であるときの価値の最大値は$ 0である。
また、その他は最大値を求めるための典型として$ -\inftyとする。
以上、これをループで回すことで配列を埋めていく形で答えを求められるため、時間計算量$ \Omicron(NW)となり、この問題を解けた。
なお、$ Wを超えるような重みについて考える必要はない。
例題
4. 高速化テクニックについては他の記事を参照されたい。
なお、この解説は短時間で殴り書きしたものであり、あまり良いものではないので、以下のスライドを参照されたい。