内容別リスト/高速化系/動的計画法 - 競技プログラミング用 知識集積所【7/10更新】

---

雑な説明

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

レベル

ABCのC問題以降。
ただし、応用の幅が広く、内容によっては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つもない状態（明らかにすぐ解ける）から初めて、その結果を継承しながら少しずつ大きな問題に答えていくことで答えが出るとわかる。
具体的には、この表を上から順に埋めていけばよい。

	合計
数列	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
なし	o	x	x	x	x	x	x	x	x	x	x	x	x	x	x	x
5	o	x	x	x	x	o	x	x	x	x	x	x	x	x	x	x
5,9	o	x	x	x	x	o	x	x	x	o	x	x	x	x	o	x
5,9,7	o	x	x	x	x	o	x	o	x	o	x	x	o	x	o	x
5,9,7,2	o	x	o	x	x	o	x	o	x	o	x	o	o	x	o	x
5,9,7,2,4	o	x	o	x	o	o	o	o	x	o	x	o	o	o	o	o

黄色：「{5,9}で13を作れるか？」は{5}で4も13も作れないのでx。
緑色：「{5,9,7}で1を作れるか？」は{5,9}で1を作れないのでx。（1<7なので、-6を作れるかどうかは見ない）
青色：「{5,9,7,2}で11を作れるか？」は{5,9,7}で9を作れるのでo。
赤色：「{5,9,7,2,4}で7を作れるか？」は{5,9,7,2}で7を作れるのでo。
といった感じ。
最終的に、元の問題には、表の右下を見て答えればよい。

この部分和問題では「合計がiであるような選び方ができるか？」を表すvector（未作成）<bool>のデータを継承しながら数列の要素を1つずつ増やしていった。
しかし、問題によっては普通に整数1つだけを継承したり、vector（未作成）<int>を継承したり、文字列を継承したり、二次元vector（未作成）を継承したりする。
増やしていく内容も数列を長くしていく以外にもいろいろあるどころか、2方向に増やしていくこともある。
見るのも1段上だけではなく2段上を見たり今までのを全部見たりする。

「何をどう増やしていくのか？」「継承するデータは何か？」の選び方が問題によって本当に幅広く変わってくる。
DPまとめコンテストにある程度パターンがそろっているので有名パターンには慣れておきたい。

注意点

表のサイズに注意。

動的計画法でデータを書き込む表のサイズは1億くらいが限界で、それを超えると計算時間が足りなくなる。
そのため、実装前に「この解法だと表のサイズはいくつくらいにいなるか？」を必ず確認する必要がある。
さらに言うと、同じ問題を各数値の制約に合わせて全く異なる方法で解かなくてはいけない場合がある。

例えば、ナップサック問題。
ざっくりいうと、

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

という問題。
それぞれがlong long型に収まるくらいの値だとして、追加の制限により解き方が大きく変わる。

Nの上限	Wの上限	w[i]の上限	v[i]の上限	その他制約	使える解法
20くらい	ー	ー	ー	ー	bit全探索（未作成）
40くらい	ー	ー	ー	ー	半分全列挙（未作成）
ー	1億/Nくらい	ー	ー	v[i]=w[i]（※1）	部分和問題用の動的計画法
ー	1億/Nくらい	ー	ー	ー	動的計画法
ー	ー	ー	1億/N^2くらい	ー	双対性（未作成）を利用した動的計画法
ー	ー	ー	ー	答え上限が1億/Nくらい	双対性（未作成）を利用した動的計画法
10^5くらい？	ー	ー	ー	v[i]/w[i]が広く分布	分枝限定法（未作成）
10^7くらい	ー	ー	ー	AHCでの出題	貪欲法（ヒューリスティック系）（未作成）
ー	ー	ー	ー	何らかの制約	制約に合わせて
ー	ー	ー	ー	ー	（未解決問題）

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

ぶっちゃけ、動的計画法ですらないものも多い。
「今回のこの制約は動的計画法なのか」からよくわからないのが、このアルゴリズムの真の難しさである。

関連アルゴリズム

メモ化再帰（未作成）

アルゴリズム自体は全く違うものだが、「こういう場面で役に立つ」はほぼ同じ。
再帰的な問題を、ボトムアップで解くのが動的計画法、トップダウンで解くのがメモ化再帰（未作成）である。
動的計画法で解ける問題はメモ化再帰（未作成）でも解ける問題が多く、逆もまた然り。

bitDP（未作成）

bit全探索（未作成）の考えを動的計画法に組み込んだもの。
N（最大20個くらい）の順序を考えたり、N個の条件を全部満たすための方法だったり、そういうのを求める際に用いられることが多い。

区間DP（未作成）

各データに対する動的計画法ではなく、各範囲を対象に動的計画法を行うもの。
範囲の左端か右端かがどうのこうの、みたいな問題で用いられることが多い。

最長増加部分列（未作成）

数列の一部（連続でなくてもよい）を拾って単調増加列を作るとき、最長でどのくらいの長さのものを作れるか？という問題。
動的計画法の応用で解ける。

最長共通部分列（未作成）

2つの数列または文字列の一部（連続でなくてもよい）を拾って全く同じ数列または文字列を作るとき、最長でどのくらいの長さのものを作れるか？という問題。
動的計画法の応用で解ける。