　動的計画法（DP）は有向非巡回グラフ（DAG）上で分配法則を用いて一括計算を行うことにより、目的の値を高速に計算することだと考えられます。この参考記事が詳しいです。厳密には違っているらしいですが。

　しかし、参考記事にあげられている例は全て重みなしグラフです。DP の典型的な問題としてナップサック問題は、このような例には当てはまりません。本記事では、この点を中心に考察を進めていきます。

全探索から貪欲へ

　そもそも動的計画法とは何ぞや、というのをお気持ちの段階から整理するため、最初は基本的な話からします。

　以下のような問題を考えてみます。AOJ の Coin Changing Problem を一部改変しています。

「額面が $c_1,c_2,...,c_m$　円の $m$ 種類のコインを使って、 $n$ 円以上を支払うときの、コインの最小の枚数を求めて下さい。各額面のコインは何度でも使用することができます。」
入力
$n$ $m$
$c_1 c_2 ... c_m$
入力例
15 6
1 2 7 8 12 50
出力例
1

　とりあえず全探索を考えます。それぞれ 16 枚以上使うことはなさそうなので、各コインを 0～15 枚使うかで、$16^6$ 通り......なんて必要はありませんね。50 円玉が一番価値が高いんだから、思考停止でこれを使っていけばいいです。という訳で答えは 1 枚。

　では、問題文を少し変えて以下だとどうでしょう（こちらがオリジナルです）。

「額面が $c_1,c_2,...,c_m$　円の $m$ 種類のコインを使って、 $n$ 円ちょうどを支払うときの、コインの最小の枚数を求めて下さい。各額面のコインは何度でも使用することができます。」
入力
$n$ $m$
$c_1 c_2 ... c_m$
入力例
15 6
1 2 7 8 12 50
出力例
2

　貪欲に考えます。

まずは一番残り金額を減らせる 12 円玉を使う。
残りは 3 円。次は 2 円玉を使う。
残りは 1 円。次は 1 円玉を使う。

　よって答えは 3 枚......ではありません。答えは「7円玉、8円玉」の 2 枚です。「ちょうど」という条件が増えたせいで、その時一番価値が高いものを使うのが最善手になるとは限らないのです。

　ここでようやく DP 的発想が必要になります。

DP のお気持ち（分配法則編）

　そもそも、DP をする動機について考えていきます。

　大前提として、十分な計算時間があれば、すべての問題は全探索により解けます。しかし、全探索では $N$ が増えてくると天文学的な時間がかかるため、ほとんどの問題では何らかの高速化が必要になります。これは DP というか、ほぼすべての競プロの問題に共通することです。そこで上手く貪欲解を見つけられない場合、DP が視野に入ってきます。

　ここでカギとなるのが、複数の状態を同一視して計算を一括化することです。1 円玉と　7円玉を 1 枚ずつ持って 8 円を所持していることと、8 円玉を 1 枚持って 8 円を所持していることは、「8 円を所持することは可能か」という問題に対しては本質的な違いを持ちません。（対して、例えば「何枚の硬貨」を所持しているか、という問題に対しては違いを持ちます）

　そのような重複した状態に対して、足し算や最小値を取るといった操作は一括して行うことができます。$(A+B+C) = A + (B+C)$、$\min(A,B,C) = \min(A,\min(B,C))$ といった形で、分配法則が成り立っているので。なので、重複した状態に対してそのような操作を続けていけば、必要な数値だけを効率よく計算していけます。

　問題に対して必要のない情報を捨象することにより、計算を高速化しているので、動的計画法は捨象された状態に対する全探索と言えます。

DP のお気持ち（トポロジカル編）

　各状態に対して遷移を定義すれば、これはノードにエッジを貼ったグラフと見なせます。であれば、目的のノードに対して最短距離を求めるなり、最長距離を求めるなり、経路総数を求めるなりして求める答えが出せます。上のコイン問題では最短距離が答えにあたります。DP テーブルは以下のようになります。

0,-,-,-,-,-,-,-,-,-,-,-,-,-,-,-,
0,1,-,-,-,-,-,-,-,-,-,-,-,-,-,-,
0,1,1,2,-,-,-,-,-,-,-,-,-,-,-,-,
0,1,1,2,-,-,-,1,2,2,3,-,-,-,-,-,
0,1,1,2,-,-,-,1,1,2,2,3,-,-,-,2,
0,1,1,2,-,-,-,1,1,2,2,3,1,2,2,2,
0,1,1,2,-,-,-,1,1,2,2,3,1,2,2,2,

　金額が大きければ必要な枚数も大きい......とはならないので（捨象した上で）全探索的発想が必要です。

　一般的には、最短距離ならダイクストラ（重みなしなら BFS）、最長距離ならベルマンフォード、といったように、グラフに対する答えを求めるには追加のアルゴリズムが必要ですが、DP ではそのような面倒なことはしません。なぜか。遷移が一方通行であるなら、グラフは DAG でありトポロジカルソート可能だからです。なので、末端から min なり max なり + を繰り返していけば、正しい答えが出てくることとが保証されます。

　参考記事で、DP は DAG 上の探索だと言っているお気持ちはここにあります。

DP が必要な場面その 2

　上のコイン問題では、「ちょうど X 円」という状態を求めるために、貪欲では無理だから DP が必要でした。

　他にも、単純な貪欲ではダメだという例があります。それは「貪欲条件が相反する時」です。A は最小化したいけど、B は最大化したい、という時です。アルゴ式のナップサック問題から引用します。

カメのアルルは、$1$ つの箱と $N$ 個のボールを持っています。ボールには $0$ から $N−1$ までの番号が振られており、ボール $i$ の重さは $W_i$、価値は $V_i$です。アルルは箱にいくつかのボールを、重さの合計が $M$ 以下となるよう番号の小さい方から順に入れようと考えています。このとき、箱の中に入っているボールの価値の合計は最大でいくつになりますか。
入力
$N$ $M$
$W_0$ $W_1$ ... $W_{N−1}$
$V_0$ $V_1$ ... $V_{N−1}$
入力例
4 15
5 5 5 12
8 9 10 24
出力例
27

　そう、皆大好きナップサック問題です。

　DP は捨象した状態に対する全探索である、という点に立ち返ると、素朴な発想は「状態を増やせばいい」です。すべての重さと価値に対して状態を定義し、それらの間に辺を貼ると、これまでと全く同じ議論ができます。計算量も、品物に対する全探索 $O(2^N)$ から、各品物の重さの最大値 $W$ と各品物の価値の最大値 $V$ を用いて $O(NW \cdot NV) = O(N^2WV)$ まで下がります。これを解法 1 とします。

　しかし、多くの問題ではこのような DP では状態量が多すぎて間に合いません（実際の提出。大きい入力で RE します）。そこで、値に意味を持たせる、という発想が出てきます。ようやく本記事の本題に近づいてきました。
　

DP の値に意味を持たせる

　重さについては全探索を行い、価値は一つの値だけ残すという方針を考えます。こうすれば計算量は $O(NW)$ まで落ちます。これを解法 2 とします。

　問題は、どんな値を残すかです。この場合、ある重さに複数の価値を持つ経路が存在する場合、一番大きな値だけ残せばいいことは、問題の意図から考えてほぼ自明です。つまり、この値は貪欲に決められます。

　ここで、ようやく見慣れたナップサック問題の解法が出てきます。DP テーブルは以下のようになります。

0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,8,8,8,8,8,8,8,8,8,8,8,
0,0,0,0,0,9,9,9,9,9,17,17,17,17,17,17,
0,0,0,0,0,10,10,10,10,10,19,19,19,19,19,27,
0,0,0,0,0,10,10,10,10,10,19,19,24,24,24,27,

　このように遷移を定義した場合、今まで違って、グラフは重みつきグラフになります。つまり、DP のグラフは、値に意味を持たせる＝辺に重みを持たせることによって、付加的に情報を追加できます。ナップサック問題は、グラフ問題として考えると、重み付きDAGに対する最長距離を求める問題ともいえます。

添字と値の違いは？

　単純な貪欲では不可能だったナップサック問題を、

解法 1 では添字を増やすことによって
解法 2 では辺に重みを持たせることによって

　可能にしました。ここで、添字を増やすのと値を増やすのと、どちらが一般的に有効かということが気になります。

　添字を増やす方法のデメリットは、配列を確保する必要がある点です。それだけメモリも増えますし、ループも増えるので、メモリ超過や時間超過の危険性も増えます。また、マイナスの小数の添字も不可能です。

　対して、辺に重みを持たせる手法では、配列を確保する必要はありません。型の範囲内であれば、マイナスや小数も保持可能です。その代わり、各ノードに 1 つの値しか保持できないので、「どれを残すのが最善か」がわかっていないと正しい答えが出ません。

　例えば、「ちょうど X になる」というような問題は、辺に重みを持たせる手法では解決できません。これは、コイン問題で述べた「『ちょうど』という条件が増えたせいで、その時一番価値が高いものを使うのが最善手になるとは限らない」と全く同じ状況です。ナップサック問題がこれで上手くいくのは「価値を最大化する」という貪欲性がはっきりしているからです。

　以上を踏まえると、ナップサック問題の解法 2 は、重さ、価値という条件に対して、片方を全探索、片方を貪欲探索することにより高速で計算しているといえます。

　現実的には、ある程度以上の難易度を持つ DP の問題で「添字を増やして多重ループを回せば済む問題」というのはほとんど出るはずないので、競技としてクリティカルに問われているのはこの貪欲化の部分と言えます。

添字と値の入れ替え

　添字を増やすことの弱点は、それに応じた配列の確保が必要なことでした。まさにこの弱点をついた問題として、ナップサック問題の制約を変えたバージョンがあります。E - Knapscak2 です。

　重さの制約が $10^9$ と、とても大きいので、解法 2 を使用する場合でも、メモリ超過してしまいます。

　代わりに価値の制約が小さいのがミソになっていて、想定解では添字と値の入れ替えを行います。つまり、「ある重さ以下に対して最大の価値を求める」という問題を「ある価値に対して最小の重さを求める」という問題に読み替えるのです。これを解法 3 とします。

　なんだか急にテクニック的な話になってきました。このような入れ替えは常に行えるのか、このような入れ替えが自然に行える条件は何でしょうか。

　結論としては、「添字であった数字が、貪欲に選べるものである場合は入れ替え可能」 です。

　逆に、「値であった数字を添字にしていいか」は考える必要がありません。添字になる数は全探索できるからです。

　つまり、

解法 2 では重さを全探索し、それに対する価値を貪欲（最大）に探索
解法 3 では価値を全探索し、それに対する重さを貪欲（最小）に探索

　しています。

　これができなくなるような条件は、貪欲に選べないことです。つまり、以下のような問題では添字と値の入れ替えはできません。（実際の提出。サンプルは通っていますが、後続のテストケースで落ちています。）

$N$ 個の正の整数 $A_0$,$A_1$,…,$A_{N−1}$ と正の整数 $M$ が与えられます。総和が $M$ となるようにいくつかの整数を選ぶ方法を考えます。選ぶ必要のある整数の個数の最小値を求めてください。ただし、総和を M にすることができない場合は −1 と出力してください。
入力
$N$ $M$
$A_0$ $A_1$ … $A_{N−1}$
入力例
7 100
1 2 4 8 16 32 64
出力例
3

0,0,0,0,0,0,0,0,
0,1,1,1,1,1,1,1,
0,2,3,3,3,3,3,3,
0,4,6,7,7,7,7,7,
0,8,12,14,15,15,15,15,
0,16,24,28,30,31,31,31,
0,32,48,56,60,62,63,63,
0,64,96,112,120,124,126,127,

　コインを $i$ 枚目まで見た時、$j$ 枚まで使うと最大何円まで増やせるか？　という DP テーブルです。

　本来なら $4+32+64=100$ という組み合わせが選べますが、間違った貪欲で選択肢を潰してしまったがゆえに、この方法では「ちょうど 100 は不可能」という判定になっています。

問題の分類

　DP の問題を DAG 上の探索と見なしたとき、重みなし／重みつきか、また行う演算によって問題を色々分類することができます。代表的な例を以下に記します。

演算	重みなしグラフ	重みつきグラフ
最長距離（`max`）	コイン問題（枚数最大化）等	ナップサック問題（重さ全探索）等
最短距離（`min`）	コイン問題（枚数最小化）等	ナップサック問題（価値全探索）等
総経路数（`+`）	コイン問題（選び方の数）等	確率DP　等

　それぞれ個別に見ていきます。

重みなしグラフ

　重みなしグラフを構築する場合、問題に必要な状態すべてを DP テーブルに記録することになります。また、ある状態に至るまでのパスの総数を数えることにより、ありえる場合の数を答えることもできます。

重みなし最長距離の例

コイン問題で、ある金額に対して使用する枚数を最大化

重みなし最短距離の例

コイン問題で、ある金額に対して使用する枚数を最小化

問題：
最小個数部分和問題

重みなし総経路数の例

　最長距離でも最短距離でも判別可能ですが、便宜上「到達可能かどうか」の問題をここに入れています。DPテーブルに true/false を埋めていくことでもできますが、総経路数を数えて 1 以上かで判別するのも計算量が変わらないので、ここに統一します。

コイン問題で、ある金額が実現可能か
コイン問題で、ある金額を実現する硬貨の選び方の数
本記事で解説したナップサック問題の解法 1
フィボナッチ数列
最長共通部分列
最長増加部分列（末尾を添字にする）

問題：
部分和数え上げ問題
 フィボナッチ数列
 F - LCS
Longest Increasing Subsequence

重みつきグラフ

重みつき最長距離の例

本記事で解説したナップサック問題の解法 2

問題：
D - Knapsack 1

重みつき最短距離の例

本記事で解説したナップサック問題の解法 3
最長部分増加列（長さを添字にするパターン）

問題：
E - Knapsack 2
Longest Increasing Subsequence

重みつき総経路数の例

　重みつきグラフだと、「総経路数＝場合の数」とは言えなくなってしまいます。このような計算を行うことはあるのでしょうか。実は、確率DPというものがそれに当たります。各ノードの存在確率を足し合わせることにより、ある状態の確率や期待値を計算していくようなイメージです。

問題：
I - Coins

まとめ

　今までの内容をまとめると、DP に至る流れというのは以下のようになります。

全探索で解けるなら、それに越したことはない
それが無理なら、貪欲で解けるに越したことはない
それが無理なら、状態を捨象して全探索を試みる
（必要なら）貪欲化できる部分については、辺に重みを持たせて DP テーブルを効率化する
（必要なら）それでも DP の構築が難しい場合、添字と値を入れ替えるとよくなることもある
トポロジカルに値を埋めていって、答えを出す

動的計画法（DP）と重みつきグラフ、あるいは添字と値の入れ替えについて