何の話かというと
（とある事情があって）「DP（動的計画法）の心」がうまく伝わるように説明したいですよねぇ・・・・という会話をしていて、まずは、古典的なナップサック問題を例に取り上げましょうか・・・と思って、適当な過去問を探していて、上記の問題に遭遇したのですが、これが意外とよくできた問題で、
・愚直にDPを実装すると実行時間制限（場合によっては、メモリー容量制限）に引っかかるので、愚直なDPの中身をよくよく理解した上で、どこで時間がかかっているのかを理解して、実行時間を削減する工夫をうまく入れないといけない
という感じになっているんですね。
で、一晩かかって、こちらの実装に辿り着いたので、どういうプロセスでこの実装にたどりついたのかを解説しながら、「DPの心」、というか、実際のところDPがどのように機能しているのか、をうまく伝えられないかを試してみようという記事です。（パチパチパチ）
DPの考え方
まずは、基本的な考え方ですが、「N個の〇〇に対して・・・・」という問題が与えられた時に、いきなり大きな N で考えるのはつらいので、まずは、一番簡単な N=1 の場合（どれか1個のデータをピックアップした場合）の答えを速攻で求めてしまいます。で、その答えが分かった前提で、N=2 の場合（正確には、N=1 の場合にピックアップしたデータに対して、さらにもう1つのデータをピックアップして加えた場合）の答えを求めます。この時、N=1 の結果をどのように再利用するかをよく考えます。さらに次は、N=1 と N=2 の答えが分かった前提で、3個目のデータを加えた場合の答えを求めます。
ということを繰り返していると、一般に、「1 〜 n-1 個のデータに対する答え」を利用して、さらにもう1つのデータを加えた「n 個のデータに対する答え」を導く方法が思いつくかも知れません。（思いついてください。）
これが思いついてしまえば、後は、この処理をループで繰り返せば、N がどれほど大きくても、N 回のループ処理で必ず回答に辿り着くことができます。テンプレート的なコードはこちらになります。（小文字の n と大文字の N は別の変数なので注意してください。）
dp[1] = xxxx # 1個の場合の答えを自力で考えて入力する for n in range(2, N+1): dp[n] = transition(dp, n) # dp[1] ... dp[n-1] の情報を使って n 個の場合の答え dp[n] を計算する関数 print(dp[N])
一般に、dp[1] ... dp[n-1] を使って dp[n] を求める計算を遷移処理と呼んだりもします。
ここで、次の問題を上記のテンプレートに当てはめて解いてみましょう。
[例題]
個の整数
が与えられている時に、これらの合計の値を計算しなさい。
はい。DPを使うのはおこがましい様な例ですが、上記のテンプレートになれる練習だと思ってください。答えはこちら。
N = 6 A = [None, 3, 1, 4, 1, 5, 9] dp = [None] + [0]*N dp[1] = A[1] # N=1 の場合 for n in range(2, N+1): dp[n] = dp[n-1] + A[n] # 遷移処理 print(dp[N])
リスト A と dp の先頭の要素が None になっているのは、リスト A[n] のインデックス n と の添字
を一致させるためです。プログラミング言語は添字が 0 から始まるのに、数学は添字が 1 から始まるんですよね・・・・。
なお、さきほどのテンプレートでは、遷移処理を transition(dp, n) という関数で表現しましたが、この関数の中でつかってよい情報には制限があります。（ここめっちゃ重要なポイントです。）それは、dp[1] ... dp[n-1]、および、A[n] です。dp[1] ... dp[n-1] を求める際にかつて利用した A[1] ... A[n-1] は、この段階では、もはや使うことはできません。（ていうか、A[1] ... A[n-1] と A[n] を用いて答えが出せるなら、DPなんか使わなくても、いきなり、一般の n の答えを求める方法がわかってることになりますよね。）
もうちょっと一般的なDP
上記の例題だと、DPって、ほんとーに簡単な考え方のように思えますが（実際、考え方自体は簡単なんですが）、もう少し一般的には、特定の n について、1つの答え dp[n] を求めるのではなく、条件を変えた複数の答え dp[n][m] を求める必要があります。（添字 m が条件の違いを表します。）
冒頭に示した有名なナップサック問題が、まさにこれに当たります。
・1個目の荷物：価値 v[1]、重さ w[1]
・2個目の荷物：価値 v[2]、重さ w[2]
・N個目の荷物：価値 v[N]、重さ w[N]
が与えられたデータで、ここから、重さの合計が W 以下になる条件で荷物をピックアップした時に、価値が最大になる組み合わせを見つけて、その時の価値の値を答える必要があります。（この問題の場合は、組み合わせそのものは答える必要がなくて、価値の最大値だけを答えればOKです。ここがちょっとしたポイントになります。）
で、テンプレートにしたがって考えると、まずは、1個目の荷物（価値 v[1]、重さ w[1]）だけが与えられたデータだと仮定して問題を解きます。簡単ですね。
・w[1] <= W なら dp[1] = v[1]
・w[1] > W なら dp[1] = 0
が答えになります。コードで実装するならこうなります。
if w[1] <= W: dp[1] = v[1] else: dp[1] = 0
なのですが・・・・
実は、この答え dp[1] だけが分かっていても、次のケース、つまり、2個目の荷物を加えて、
・1個目の荷物：価値 v[1]、重さ w[1]
・2個目の荷物：価値 v[2]、重さ w[2]
だけが与えられたデータと仮定した問題を解くための十分な情報にはなりません。先ほど、説明したように、この段階で使ってよい情報は、
・dp[1]、v[2]、w[2]
だけである点に注意してください。問題の想定としては、1個目と2個目の荷物がある場合の問題を解いているのですが、DP の手続きとしては、（dp[1] の他には）2個目の荷物の情報しか使えないのです。
そうすると、何が困るかというと、2個目の荷物を入れるべきかを判断する際に、1個目の荷物が入っていたとして、ナップサックの残り容量（W-w[1]）が w[2] 以上あるかを考慮する必要がありますが、dp[1] にはそのような情報は含まれていません。
どうしよう。。。。。
ここで登場するのが、「条件を変えた複数の答え dp[n][m] を求める」という発想です。いまの場合、何が条件かというと、ナップサックの容量 W です。本来解きたいのは、ある特定の W に対する問題なのですが、DP を考える場合は、「さまざまな W について、全部の場合を解いてしまう」ことを考えます。「全部の場合」というと、範囲が無限にあってこまってしまいますが、今の場合は、（荷物の重さはすべて自然数という前提で）ナップサックの容量が の
種類のケースを考えればOKです。
なぜこれでOKと分かるの？？？？ と思う方もいるはずですが、実は、ここがDPの難しい所で、どういう条件を網羅すればよいかというのは、一般論は無くて、与えられた問題ごとに試行錯誤で見つけ出すしかありません。で、だいたいの場合は、「おまえそれ良く思いついたなぁ。。。。」的な「とんち問題」っぽいものになってるんですよね。。。。まぁ、ここは、DPとはそういうもんだと割り切って、沢山の典型例を見て、感覚をつかんでいくしかないでしょう。
で、今の場合は、こんな感じになります。まず、1個目の荷物だけが与えられた場合の答えを改めて求めると、こんな感じのループになります。
for w0 in range(0, W+1): if w[1] <= w0: dp[1][w0] = v[1] else: dp[1][w0] = 0
ナップサックの容量 w0 についてのループで、w0 = 0, 1, ..., W のすべての場合の答えを個別に dp[1][w0] に格納しています。
それでは、この情報を用いて、
・2個目の荷物：価値 v[2]、重さ w[2]
を追加した場合の答え dp[2][w0] について考えてみましょう。
いま、求めるべきものは、「価値の合計が最大になる入れ方（その場合の価値の合計値）」なのですが、論理的に考えて、「2個目の荷物を入れない場合」か「2個目の荷物を入れる場合」のどちらかがその答えになるはずです。そこで、
・2個目を入れない前提で達成できる最大価値 ----- (1)
と
・2個目を入れる前提で達成できる最大価値 ----- (2)
のそれぞれを個別に計算して、得られる最大価値の大きな方が、本当の意味での正解、ということになります。（(2) の計算をする時に、「そもそも2個目は絶対に入れられない状況だとどうすんの？」と思うかもしれませんが、そういう場合は最大価値を 0 とすればOKです。(1) の方の最大価値は 0 より大きくなるはずなので、最後の比較でちゃんと (1) の場合が選ばれます。）
で、(1) の場合の答えを考えるわけですが・・・・そう！これはもう分かっています。2個目の荷物は無視して、1個目の荷物だけで価値を最大にする方法を考えればよいので、先に計算した dp[1][w0] がその答えになります。1個目の荷物の具体的な情報（w[1]、v[1]）は使わずに、d[1] の情報だけで答えが得られました。これこそが「DPの心」になるわけです。
ではでは、(2) の場合はどうなるのでしょうか？ まず、w[2] > w0 の場合は、（1個目の荷物を入れたかどうかに関係なく）そもそも2個目の荷物を入れることは不可能ですので、お約束により最大価値は 0 になります。一方、w[2] <= w0 の場合は・・・・。うーん。1個目の荷物を入れたかどうかで、結果がかわるよなぁ。。。うーん。。。。
・・・・通常の思考では、こうなるのですが、ここで、ちょっとだけ発想を逆転します。今はとにかく、2個目の荷物を入れるという大前提で考えているわけですので、まず、からっぽのナップサックを用意して、先に2個目の荷物を入れてしまいます。すると残りの容量は w0-w[2] になりますので、この（ちょっとだけ容量が小さくなった）ナップサックに、1個目の荷物を入れるかどうかを判断すればよいのです。例によって、1個目の荷物の具体的な重さ w[1] の情報は使えないので、1個目の荷物が入るかどうかわからないのですが、そこは心配ありません。いま欲しい情報は、「1個目の荷物だけ与えられた状況で、容量 w0-w[2] のナップサックに対して、最大価値を実現する入れ方」です。
そう！これはもう分かっています。先に計算した dp[1][w0-w[2]] がその答えじゃないですか。というわけで、先に入れた2個目の荷物の価値 v[2] とあわせて、「dp[1][w0-w[2]] + v[2]」が (2) の答えになるわけです。
というわけで (1) (2) のそれぞれがわかったので、比較して大きな方を dp[2][w0] の答えに採用することができます。コードにまとめるとこんな感じでしょうか。
[code01]
for w0 in range(0, W+1): case1 = dp[1][w0] if w[2] > w0: case2 = 0 else: case2 = dp[1][w0-w[2]] + v[2] dp[2][w0] = max(case1, case2)
ここまで、特定の w0 について考えていましたが、実際には、w0 = 0,1,...,W のすべてのケースを考えないといけないので、上記のコードでは気を利かせて、w0 のループを回しておきました。
DPの心がつかめて来たでしょうか・・・・
次は、3個目の荷物を含めた場合にいくのですが、このままではキリがないので、一般の n について考えましょう。n-1 個目までの荷物だけを使った問題がすでに解けている、すなわち、
・dp[1][0], dp[1][1], ..., dp[1][W]
・dp[2][0], dp[2][1], ..., dp[2][W]
・dp[n-1][0], dp[n-1][1], ..., dp[n-1][W]
を利用できるという前提で、n 個目までの荷物を容量 w0 のナップサックに詰める問題を解いてみましょう。考え方は、2個目の場合と同じです。
・n個目を入れない前提で達成できる最大価値 ----- (3)
と
・n個目を入れる前提で達成できる最大価値 ----- (4)
のそれぞれを個別に計算して、得られる最大価値の大きな方を選べばOKです。
で、(3) の場合は、「n-1 個目までの荷物を容量 w0 のナップサックに詰める問題」と同じですので、答えは、dp[n-1][w0] です。
(4) の場合は、容量 w0 の空のナップサックに先に n 個目の荷物を入れてしまって、残った「容量 w0-w[n] のナップサックに対して、 n-1 個目までの荷物を使って、最大価値を実現する入れ方」を考えればよく、その答えは dp[n-1][w0-w[n]] です。n 個目の荷物の価値とあわせて、(4) の答えは「dp[n-1][w0-w[n]] + v[n]」と決まります。おっと、先走りました、これは、w[n] <= w0 の場合ですね。w[n] > w0 の場合は、お約束で 0 です。
これらの大きい方を採用すればよいので、コードにすればこうなります。
[code02]
for w0 in range(0, W+1): case1 = dp[n-1][w0] if w[n] > w0: case2 = 0 else: case2 = dp[n-1][w0-w[n]] + v[n] dp[n][w0] = max(case1, case2)
さきほどの [code01] と比較すると、1 -> n-1、2 -> n のきれいな置き換えになっていることがわかります。ですので、このコード（[code02]）を n=2,3,...,N まで繰り返せば、無事に dp[N][0],...,dp[N][W] が計算できます。このループも明示的にコードにしちゃいましょう。
# n = 1 の場合 for w0 in range(0, W+1): if w[1] <= w0: dp[1][w0] = v[1] else: dp[1][w0] = 0 # n = 2,...,N の場合 for n in range(2, N+1): for w0 in range(0, W+1): case1 = dp[n-1][w0] if w[n] > w0: case2 = 0 else: case2 = dp[n-1][w0-w[n]] + v[n] dp[n][w0] = max(case1, case2)
ここでは、ずっと（？）以前に書いた1個目の荷物だけの答え dp[1] を求めるところもくっつけてあります。ほぼ完璧なコードですね。
で・・・、今、沢山の dp[N][0],...,dp[N][W] が出て来ましたが、一番最初の問題は、容量 W のナップサックに N 個目までの荷物を詰める場合なので、この中でも dp[N][W] が本当に欲しかった答えということになります。
せっかくなので・・・提出して結果を見てみましょうか？
はい。いくつかのケースはパスしていますが、実行時間オーバー、メモリーオーバー、ランタイムエラーまで、いろいろ大変なことが起きています。上記のコードは、論理的には正しいのですが、リスト dp[ ][ ] が巨大になりすぎるという欠点を抱えているのです。N と W の範囲を見ると、 と書かれており、dp[ ][ ] は最大で、
ものサイズになります。そりゃあランタイムエラーも起きる気がしますよね。
次回の記事では、巨大な配列を使わずに、これと同等（類似）のロジックを実装する方法を考えてみたいと思います。
おまけ
上記の提出コードを見ると、
import sys def main(f): v, w = [None], [None] N, W = list(map(int, f.readline().split())) for _ in range(N): v0, w0 = list(map(int, f.readline().split())) v.append(v0) w.append(w0) .... main(sys.stdin)
という形式で、標準出力をファイルとして開いて入力データを読み出す形にしています。こうしておけば、最後の main(sys.stdin) を
with open('input.txt', 'r') as file: main(file)
と書き直すことで、本物のファイルからの読み出しに切り替えることができます。普段は Colab でコードを書いているので、Colab で実行する際は、こんな感じで利用しています。
