44. 動的計画法(DP)についての話

最近は競技プログラミング用のライブラリをチマチマと作っているのですが、競技プログラミングは「問題に対して適用するアルゴリズムを決めて、ライブラリから引っ張れば良いだけ」…というわけでもありません。

その代表例が動的計画法（DP）の問題だと思っています。これは解答例のコードだけ見ると非常にシンプルになることが多いです。それこそ二重ループしか回していないようなレベルで。しかし、（自分を含めて）苦手とする人も多く、つまり「方針を立てるところが全てで、かつ、それが難しい」ということです。

では、何故難しいと感じるのかと言えば、今のところ自分の中では「普通に考えるのと逆側から見る必要があるから」という結論があります。別の表現をすれば、スタートではなくゴールから考える必要があるのです。これに気付くまでは、どうして解答例がそのような発想に至ったのか理解しづらいと思います。

具体的に「ナップサック問題」という有名問題を考えてみます。

$N$ 個のモノがあって、それぞれ $1, 2, \cdots, i, \cdots, N$ とラベルが振られている。
ラベル $i$ のモノは、重さ $w_i$ 価値 $v_i$ を持っている。
あなたは重さ $W$ までナップサックにモノを入れることができる。
価値の合計が最大となるようにナップサック内へモノを入れると、その合計価値はいくらになるか？

スタートから単純に考えると、「モノ 1 を取る」「モノ 1 を取らない」という2状態から始まり、そこから次のモノを「取る・取らない」で2状態作り…と、価値合計が最大となる状態を探す探索問題になります。しかし、この探索方法では見るべき状態数が $O(2^N)$ となり、相当厳しいことがわかります。

そこで、逆転の発想としてゴールから考えます。つまり、「モノ $N-1$ までについては最大価値が既に分かっているとして、モノ $N$ について考えよう」というわけです。

モノ $N-1$ まで探索した結果の最大価値が $V_{N-1}$ だったとします。どのようにモノを選択してきたのか、ということは考えません。とにかく、ここまでは問題で問われている内容（最大価値）が分かっているものとして扱います。

このとき、さらにモノ $N$ を考えた場合の最大価値、すなわち $V_{N}$ はどうなるでしょう？この問いに対する答えは比較的簡単に浮かぶと思います。

モノ $N-1$ まで見てきて合計の重さが $W - w_N$ 以下なら、モノ $N$ は取っても大丈夫だから $V_N = V_{N-1} + v_N$ となる。
モノ $N-1$ まで見てきて合計の重さが $W - w_N$ より大きいなら、モノ $N$ は取れないから $V_N = V_{N-1}$ となる。

このように、「どのようにモノを取ってきたか」ではなく「合計の重さがいくらになったか」という状態に依存して答えが分岐します。そのため、こちらも状態に加えて考えてやります。つまり、「 $V_{i, j} :=$ モノ $i$ までを候補にして、重さ $j$ となる場合の最大価値」と定義してやれば、

$j \le W - w_N$ ならば、 $V_{N, j+w_N} = V_{N-1, j} + w_N$
$j \gt W - w_N$ ならば、 $V_{N, j} = V_{N-1, j}$

となることが分かります（実際には2条件が重なった更新箇所では最大値を優先するなど、例外処理を考える必要がありますが、骨格となるのは上記のような発想です）。これが漸化式であり、 $V_{i, j}$ がいわゆるDPテーブルになるわけですね。

最後に、漸化式を解くために初期状態を考えてやります。モノ 1 について取る・取らない場合を考えると、 $V_{1, 0} = 0, V_{1,w_1}=v_1$ です。これで、 $V_{2, j}$ が計算できるようになったので、あとは順番に $V_{N, j}$ まで計算していけば良いです。そして、 $0 \le j \le W$ の範囲で $V_{N, j}$ の最大値が答えとなります。

このアルゴリズムだと、見るモノを1つ増やすごとにDPテーブル更新に $O(W)$ 必要なので、結局全体として $O(NW)$ の計算量になります。スタートから考える探索と比べると、ずいぶん計算量が減りました。

このように、「それまでの事は分かっているとして、最後の一手を決めるにはどうすれば良いか？」を考えるのが動的計画法であり、探索とは全く逆の発想になっています。普段なかなかしない発想なので慣れるまでが大変ですが、AtCoder には Educational DP Contest という動的計画法の問題集があるので、これで十分慣れることができると思います。

atcoder.jp

参考記事です。

shindannin.hatenadiary.com