はじめに
こんにちは、AtCoderという競技プログラミングのサイトの底辺です。今回は脱初学者を目指す私の目線から当時思ったことなどを踏まえながら、動的計画法を解説していこうと思います。なので読者は動的計画法を知らない人、名前は聞いたことあるけど理解はしてない人を対象としています。今回解説するのは部分和問題の動的計画法になるので、他の応用方法等は記載しておりません。また、ソースコードはJavaを用いて実装いたします。書いてみたところ長くなってしまったので、簡単に知りたい方はまとめのみをご覧ください。
目次
1.動的計画法とは
2.フィボナッチ数列
3.ナップサック問題
4.動的計画法の実装
5.まとめ
1.動的計画法とは
まず、動的計画法とは何なのかについて説明します。動的計画法はアルゴリズムの一種です。もちろんアルゴリズムである以上計算量を少なくできるものですが、その説明は各サイトでそれぞれ異なります。以下に動的計画法の説明について例を挙げます。
- 計算量が大きい問題を小さな問題に部分化し、それらを解くことで最終的な解を得る手法
- 結果を再利用する手法
- 途中までのベストを記録して毎回最初からやらない手法
動的計画法理解した後で読むと、確かにどれも合っていそうって感じがするんですが、最初見たときは「結局どれが正解なの？」「難しい言葉で言われてもわからん！」と思いました。
結局動的計画法とは何なのか、私は動的計画法とは「これまでの結果に基づいて最適解を求めるアルゴリズム」というのが一番腑に落ちました。しかし、動的計画法は言葉で説明されても理解しづらいと思いますので、練習あるのみです。今回は3つの例題を用意したので、こちらを使って解説していきます。
2.フィボナッチ数列
最初の例はフィボナッチ数列です。フィボナッチ数列はあるn番目の数が、その1つ前と2つ前の数を足したものになっているという性質を持つ数列です。具体的には以下のような0,1,1,2,3,5,8…という数列です。動的計画法の凄さを伝えるには、あまり良い例とは言えませんが、これまでの結果に基づいて最適解を求めるアルゴリズムというイメージを持ってもらうには1番良い例だと思います。
さて、みなさんはフィボナッチ数列を求める時どうしますか？12番目の数、上の数列で言う55の次の数を計算してみてください
計算したらここをクリック
動的計画法を使わずにコンピュータでフィボナッチ数列を求めるとき、再起関数を用いて求めます。例としてフィボナッチ数列の10番目を出力するプログラムを書きます。再起関数だと以下のようなソースコードになります
public class Fibonacci {
// fibonacciメソッドが呼ばれた回数
static int count = 0;
public static void main(String[] args) {
System.out.println(fibonacci(10)); //34
System.out.println(count); //109
}
private static int fibonacci(int n) {
count++;
if (n == 1) {
return 0;
} else if (n == 2) {
return 1;
} else {
return fibonacci(n - 1) + fibonacci(n - 2);
}
}
}
このソースコードの問題点はn番目を毎回最初から求めていることです。結局メソッドを109回呼び出すことになります。
それでは動的計画法で実装しましょう。動的計画法は今までの結果に基づいて最適解を求めるので、今までの結果の表が必要です。今回は以下のような表を使いましょう。つまりソースコードで実装するなら1次元の辞書を用意します。
この表を用いて左から埋めていきます。処理する回数は先ほどよりかなり減って19回になります。これは毎回最初から求めずに、これまでの結果に基づいて解を求めたからです。ソースコードは以下のようになります。
import java.util.HashMap;
public class DynamicProgramming {
// dpメソッドが呼ばれた回数
static int count = 0;
//結果を格納する表を辞書として登録
static HashMap<Integer, Integer> table = new HashMap<>();
public static void main(String[] args) {
System.out.println(dp(10)); //55
System.out.println(count); //19
}
private static int dp(int n) {
count++;
int result;
//結果が格納されて入ればその結果を用いる
if (table.containsKey(n)) {
return table.get(n);
}
//結果が格納されていなければ、計算して求める
if (n <= 1) {
result = n;
} else {
result = dp(n-1) + dp(n-2);
}
//計算結果を格納する
table.put(n, result);
return result;
}
}
ここまでで、動的計画法はこれまでの結果に基づいて計算するものというイメージができたと思います。ただ、これでは動的計画法すごい！ってならないので、少し難しい例題にも挑戦してみます。
3.ナップサック問題
次の例を見てみましょう。こちらは動的計画法の凄さを伝えるには良い例だと思っております。ナップサック問題とは簡単に言うと、ある条件の中で最適解を求めるという問題です。具体的には10kg入るナップサックがあります。入れたいものには重さと価値がついています。最も価値が高くなるように下の入れたいものリストから入れるものを選んでくださいというものです。
私が即興で入れたいものリスト作ってしまったので、5kgのお弁当とかが発生してますがご容赦ください。4kgのゲーム機とかPS5とかでも持っていくんですかね
さて、この中から価値の高い組み合わせをパッと求めることができますか？さっきのフィボナッチ数列の問題とは違って少し難しいのではないかと思います。この問題を解くときに動的計画法ではない例として、まず思いつくのが全通り試してみることです。
全通り試す？
それぞれの入れたいものに対して、入れる入れないの2通りがあります。入れるを〇、入れないを×として、お弁当を入れる場合だけを表すと、以下のように表せます。
それぞれの入れたいものに対して入れる入れないの2通りあるので計算量は$2^n$通りになります。今回でも$2^8$回($256$回)かかります。入れたいものリストがさらに増えて50とかになると$2^{50}$とかになって恐ろしく大きい数になってしまい、全通り試すのは現実的ではないことが分かります。
動的計画法で解こう！
それではどうすればいいのか。ここで動的計画法の出番です。今回も今までの結果に基づいて最適解を求めて行きたいので、結果の表を用意しましょう。今回は1次元の表で結果を管理することは難しそうです。ですので、2次元の表を作ります。2次元になってもやることは一緒です。横軸が重さ、縦軸には入れたいものリストの番号を書きます。こうすることで、表の中にその重さまでの中で、入れたいものリストの番号までを組み合わせてできる最大価値を入れていくことができます。この表を理解するために横軸が重さ、縦軸が入れたいものリストの番号、中身がその時点でできる最大価値ということを覚えておきましょう。2次元の場合左上から埋めていくイメージです。ちなみに何も入れないという選択肢をとれるように、1行目に0番として何も入れない選択肢を追加します。また1列目にも空っぽを意味する0番目を入れておきます。そうすると表は以下のようになります。今回だけ縦軸の入れたいものリストに名称、重さ、価値を書いておきます。
- 動的計画法では今までの結果を使うため、結果を格納する表が必要
- 今回の問題においては表の横軸は重さ、縦軸は入れたいものリストの番号、中身がその時点でできる最大価値
1行目
1行目は何も入れないので最大価値は0ですね。なので0埋めしました。下準備までがこれで終わりました。ここからが動的計画法の本番です。
2行目
次は2行目を埋めていきます。2行目はつまり、1番目まで(入れたいものリスト0,1)を使ってできる各重さでの最大価値です。この認識が今回の表を理解するために大切です、後で使うので覚えておきましょう。お弁当は重さ5kgなので、重さ4までは何も入れない選択肢しか取れません。重さ5からはお弁当を入れることができます。0(何も入れない)と1(お弁当)を組み合わせるのであれば、絶対にお弁当を入れた方が、価値が高いです。なので、重さ5~10まではお弁当の価値、10が入ります。
3行目
次に3行目を埋めます。3行目も2番目まで(入れたいものリスト0,1,2)を組みあわせてできる最大価値を入れていきましょう。重さ5まではお弁当も水筒も入らないので0です。さて、ここから大事な所になります。「重さ5の所では、お弁当か水筒を入れることができます」この文章だと現時点では分かります。しかし、後々品物が増えてくると「重さ5の所にはお弁当か水筒かお菓子かおもちゃを入れることができます」と結局何を入れるべきか分からなくなってしまいます。これは今までの結果を使っていないから です。なので、違う文章に言い替えましょう。ここで大事な前提条件としては2行目までには1番目まで(入れたいものリスト0,1)を使ってできる各重さでの最大価値が入っています。つまり、「重さ5の所はお弁当と水筒を入れることができる」という文章ではなく、「水筒を入れるか入れないか」という文章で表せます。それまでの最適解が入っているので、それを使って水筒を入れるか、入れないかのみを判断すれば良いわけですね。具体的には水筒を入れない場合の1つ上のマスの値と水筒を入れた場合の水筒の重さ分左に動いて1つ上のマスに水筒の価値を足した値を比較すれば良いです。図示すると以下のようになります。ちなみに重さ10では両方入る、つまり水筒を入れた場合を採用します。あとはこの作業の繰り返しです。
さらに細かく参照したい方は以下を押して4行目、5行目の解説へ、もう大体分かった方は最後の行に進みます。
4行目、5行目解説
4行目の解説に進みます。4行目も「お菓子を入れるか入れないか」を判断していきましょう。お菓子の重さは1、価値は5です。重さ1～4まではお菓子しか入らないのでお菓子を入れましょう(ここも厳密に言えばお菓子が入る場合と入らない場合を比較しています)。重さ5ではお菓子を入れるか入れないかの判断が必要です。さて、この時点で上のマスにはお菓子を入れない場合の最大価値(お弁当を入れる)があるので、これとお菓子を入れた場合の比較をします。図解すると以下のようになります。
重さ6~9まではお弁当にさらにお菓子を入れることができるのでこちらの方が価値が高いのは明らかです。最後のマスではまた、比較が起こります。お弁当+お菓子の組み合わせ vs お弁当+水筒の組み合わせが起こります。これで4行目が終わりました。
次は5行目です。5行目では「重さ2、価値3のおもちゃを入れるか入れないか」を判断していきましょう。重さ2の時点で早速お菓子とおもちゃの対決が始まってますが、無情にもおもちゃは重いのに価値が低いので、お菓子を入れます。その次のマスではおもちゃが入る余裕ができるのでおもちゃも入れましょう。重さ5ではおもちゃとお菓子の組み合わせ vs お弁当単騎の戦いが始まります。そのあとはまた重さ8でおもちゃも入れれるようになったら入れて、ここまで来るとマスの数字が様々になってくるのでマスの数字を入れるのが楽しくなってきました(実体験)。最後のマスではお弁当+お菓子+おもちゃ vs お弁当+水筒の激戦が繰り広げられます！まあ、やってることはおもちゃを入れるか入れないか判断しているだけなんですけどね。
最後の行
最後の行の解説に入ります。最後の行を埋める前の表は以下のようになります。
最後の行も同じように埋めていきましょう。今回入れるか入れないかを判断するものはみんな大好きゲーム機で、重さ4、価値7です。重さ3までは入らないので飛ばします。重さ4では、1つ上のマスと、左に4つずれて1つ上に行ったマスにゲーム機を入れた時を比較します。意味を付け加えると、上のマスがお菓子+おもちゃ+レジャーシートの価値で、左にずれた方を選ぶとゲーム機だけを入れた価値になります。10と7では10の方が価値が大きいので、ここではゲーム機を入れない判断をします。
逆に次のマスではゲーム機を入れた方が5+7で得します。
この感じで最後まで表を埋めていくと下の結果の表が完成しました。さて、私達が元々求めたかったものは何だったでしょうか？10kgまでの重さでナップサックに入れる物の価値が最大となる組み合わせが欲しかったんですね。これって言い換えると8番目まで(入れたいものリスト全て)を使ってできる重さ10kgの最大価値になります。この表でそれが入っているマスというのは横軸縦軸を理解してれば、すぐに分かります。そう、1番右下のマスです。あとはこの表から右下だけ取ってあげれば良いですね。無事に22という最適解を求めることが出来ました！
計算量のお話
動的計画法は基本的に表を埋めてその中から最適解を出すという手法になります。そのため、計算量は表のマスと同じになります。横軸を$w$、縦軸を$h$とします。横軸と縦軸の両方に0番目が加わるので、式にすると以下のようになります。
$計算量 = (w+1)(h+1)$
別のサイトだと+1してなかったので間違えてる…かもしれませんが、計算量を表すオーダー数にしたときは$O(wh)$となってこれは確かに合っているはずです。オーダー数は簡単に言うと大体このくらいの処理回数で計算できるよという目安で括弧の中の数字が小さいほどいいです。全通りやってたら$O(2^n)$になります。
式苦手って人は表の縦×横でできるんだなって覚えてください。具体的な数字で言うと今回であればw=10,h=8なので(10+1)＊(8+1)=99となります。もし全通りやるなら$2^8$で256回だったことを考えるとかなり高速になったことが分かります。特にもっと入れたいものリストの物が増えたらその差は明らかです。ここまでで動的計画法の凄さが伝わってくれれば嬉しいです。ちなみにこのようにある集合からいくつか選んで最適解を求めるのを部分和問題と言います。
4.動的計画法の実装
実際に動的計画法を使って1問解いてみましょう。今回はAtCoderという競技プログラミングのサイトの問題を使います。問題文とかも書きますが一応元のリンクを貼っておきますので、解説見る前に挑戦してみたい方はどうぞ。解いてみたんですけど、私のコード完ぺきではないと思うので解答例としてこういうソースコードとか考え方があるよ程度に思ってください。
問題文
高橋君は料理1から$N$の$N$品の料理を作ろうとしています。
料理$i$はオーブンを連続した$T_i$分間使うことで作れます。1つのオーブンを2つ以上の料理のために同時に使うことはできません。
2つのオーブンを使えるとき、$N$品の料理を全て作るまでに最短で何分かかりますか？ なお、オーブンを使う時間以外は無視できるものとします。
制約
- $1≤N≤100$
- $1≤T_i≤1000$
- 入力に含まれる値は全て整数である
入力
入力は以下の形式で標準入力から与えられる
$N$
$T_1$ ... $T_N$
出力
答えを出力せよ
入力例1
5
8 3 7 2 5
出力例1
13
例えばオーブン1で料理8と5、オーブン2で料理3,7,2を作れば全ての料理を13踏んで作り終えることができます
入力例2
2
1 1000
出力例2
1000
オーブン1で料理1、オーブン2で料理1000を作るので、最短でも1000秒かかります
入力例3
9
3 14 15 9 26 5 35 89 79
出力例3
138
オーブン1で料理14,35,89を作るのに138秒、オーブン2で料理3,15,9,26,5,79を作るのに137秒なので最短138秒です
解法の考え方
この例題では実際にどうやって動的計画法に問題を落とし込んでいくのかと、実装しているソースコードを理解していただけると嬉しいです。さて、これに動的計画法が使えるらしいです。この問題も、ある集合からいくつか選んで最適解を出すという部分和問題ですね。私もナップサック問題と同じ様に解いてみようとしたところ、2つの違う点に気付きました。
- 今までは最大値を取ってたけど、今回は最大値取ってもダメなのでは？
- 横軸っていくつまで取っておけばいいの？
これらの疑問についてそれぞれ入力例1を用いて考えていきます。今までは最大値を取ってそれを出力すればそれが最適解でした。今回の問題では単純に最大値を求めてもそれが最適解ではないのは明らかです。動的計画法を実装する際に考える大事なこととして、その問題において何が一番価値の高いものなのか、つまり最適解なのかを考えることが重要です。それでは今回の最適解は何なのかを考えていきます。
まずコンピュータにやらせることを考えずに自分でどう振り分けたら良いかを考えます。2つのオーブンを使って料理を作り、オーブン両方の時間を短くしたいです。片方のオーブンの使用時間を短くすれば、もう片方の使用時間は長くなります。この事から、作業を均等に分担すれば良いことが思い付きます。つまり、最適解はSの半分です。入力例1だと、合計が25なので、12か13を作れるならそれが最適解、もし作れなくても近い値(11とか14)が最適解になります。ここでオーブン1の使用時間とオーブン2の使用時間の関係を考えると、オーブン2の使用時間はSからオーブン1の使用時間を引いたものになります。つまり最適解の片方を求めれば、もう片方はSから引くことで求められます。入力例1だと12が分かれば、出力したい13の値が25-12で求められます。これらから私の解法は「S/2以下の最大値を求めて、オーブン1の使用時間とするとオーブン2の使用時間が答えになる」という方針に基づいたものになります。
さて、それではS/2以下の最大値はどうやって求めるかというと、ここで動的計画法の出番です。作りたい料理のn番目までの組み合わせでS/2以下の最大値を求める表を作りたいので、横軸にはS/2+1を取ります(0から始めるので+1しないと最適解の数が含まれない場合がある。1敗)縦軸に作りたい料理のリスト、横軸に時間をおくことで、ナップサック問題と同じように「その時間内で作ることができる料理の調理時間の最大値」を求めることができます。
計算量のお話
今回の問題ではプログラムの実行時間の制限が2秒になっています。言語や処理の複雑さによって違いはありますが目安として、処理の回数を$10^8$以内に収めることで制限時間内に実行することができます。ここで、今回の問題の計算量を考えます。計算量を考えるときは一番時間がかかるケースを想定すると良いです。今回では、Nが100で$T_i$が1000の時、一番時間がかかるケースですね。ここでTの総和のSは1001000で100000になります。動的計画法の計算量は以下の式で計算されるものでした。
$計算量 = (w+1)(h+1)$
今回は横軸wがs/2+1の、縦軸hがNなので、{(100000/2+1)+1}(100+1)= 5,050,202回の処理を今回は行うことになり、これは$10^8$より十分に小さいので、実行時間以内に動作することが確認できます。動的計画法調べている時に見たんですけど、制約がやたらと小さいなと感じた場合は動的計画法を疑った方が良いみたいですね。
コード解説
コードの解説はJavaで行います。二次元配列とかが扱えれば実装できます。早速コードを貼りますので、一旦目を通してみてください。コードの綺麗さにはあまり自信が無かったので、コメント文気持ち多めに付けてます。
import java.util.Scanner;
//動的計画法
public class DP {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
// 縦軸には0番目を追加するのでn+1のサイズを確保しておく
int[] t = new int[n + 1];
// tの合計値
int s = 0;
// 縦軸の作成と、合計値を求める
for (int i = 1; i <= n; i++) {
t[i] = sc.nextInt();
s += t[i];
}
// 動的計画法に使用する表の作成 横軸にs/2+1, 縦軸にn+1を取る
int[][] table = new int[n + 1][s / 2 + 1];
// 最初の行を0で初期化
for (int j = 0; j < s / 2 + 1; j++) {
table[0][j] = 0;
}
// 料理を作る前の横軸の座標
int putPosition;
// 料理を作った時の時間
int putWeight;
// 料理を作らなかった時の時間
int beforeWeight;
for (int i = 1; i <= n; i++) {
for (int j = 0; j < s / 2 + 1; j++) {
putPosition = j - t[i];
beforeWeight = table[i - 1][j];
// 物を入れても入らないとき
if (putPosition < 0) {
// 物を入れない場合を選択
table[i][j] = beforeWeight;
continue;
}
// 物を入れた時の重さを計算
putWeight = table[i - 1][putPosition] + t[i];
// 高い価値の方を採用
if (putWeight > beforeWeight) {
table[i][j] = putWeight;
} else {
table[i][j] = beforeWeight;
}
}
}
System.out.println(s - table[n][s / 2]);
}
}
コードの二重for文の手前までは動的計画法に必要な初期化や配列の準備、入力の読み取りなどです。動的計画法が実際に始まるのは二重for文からなのでこちらを解説します。二重for文の最初のfor文では、i=0番目が初期化されているので1～nまで回して、こちらが縦軸の番号になります。次のfor文のjが横軸の番号になります。
まず料理を作る前のPositionを見て、料理がまず作れるかどうかを判断します。例えば横軸で0,1,2,3,4,5,6,7のところで8秒かかる料理を作ることはできません。その場合は料理を作らない場合であるbeforeTimeを最適解として選びます。ナップサック問題の解説の時に入らないならそのままにすると、言ってたのがこの部分です。ここまでが二重for文の中の最初のif文までの処理で、図示すると以下のようになります。
もしpositionが配列外でなかった場合にはその料理を作る場合(cookTime)と作らなかった場合(beforeTime)を比較して価値の高い方をセルに記入します。ナップサック問題で沢山やった入れるか入れないかの判断ですね。これを最後まで繰り返し、最後のセルに格納されているのがs/2以下の最大値になるので、これをSから引いて出力することでこの問題を解くことができます。
別解
いろいろこの問題の解法について調べた結果今回私が解いた方法以外にも動的計画法を使ったたくさんの方法がありそうです。
1.s/2以上の中で作れる最小値を見つける
2.縦軸と横軸は同じでセルの中身を「その数が作れるか」にして1番最後の行から、最大値を取り出す。
3.ビット高速化
1.は解説を見た時私より賢いやり方だと感じました。今回のオーブンの使用時間の値は大きい方と小さい方があり、求めたいのは大きい方です。今回の問題の入力例1なら、12秒と13秒の2つがあり、出力するのは13秒の方です。私の場合はs/2以下の最大値(小さい方の値)を探してTの合計時間から引いてました。しかし、1.のやり方だと、s/2以上の最小値を探すので、求めた最小値がそのまま答えになります。
2.は私の解法と考えは同じですが、セルの中身が値ではなくTrue or Falseの真理値になります。そのような動的計画法のやり方もあるのだなと感じました。
3.は私は詳しく知らないので紹介程度にします。ビット演算を駆使して動的計画法を行うことで、さらに高速に処理することができるみたいですね。気になる方はこの問題の公式解説の動画でビット高速化を行っていたのでこちらを見ることをオススメします。
公式解説の動画リンク↓
https://www.youtube.com/live/ZqFtoX-W1Bk?si=KoRTfw_1t7xnVGjp
5.まとめ
動的計画法とは今までの結果に基づいて最適解を求めるアルゴリズムです。実装する際には以下の手順を行います。
1.今までの結果を格納する表(配列)を用意する
2.順に表(配列)を埋めていく
3.最適解が求まるのでそれを出力する
表に関してのまとめとしては、横軸が制約、縦軸には選ぶ物や分類する物の番号、表の中の各マスには△番目までの物を組み合わせてできる制約〇での最大価値です。
動的計画法で部分和問題を解く時は、それまでの最適解が求まっているという強力な前提に基づくことで、物を選ぶか選ばないかの2択をし続けるだけで、最終的な最適解を求められます。また、計算量を表のマスの数にすることが出来ます。
問題を解く時にはその問題における価値は何なのか、横軸にはいくつまでの数字を取ればいいのかを考えることである程度応用が可能です。
今回は動的計画法の主に部分和問題について解説しました。私もまだまだ基本的な動的計画法しか実装したことがないので、さらに応用的な所は別の方におまかせします。この記事を読んで動的計画法を知らない所から、理解する所、実装できる所まで到達できた方がいれば幸いです。閲覧いただきありがとうございました。
参考文献
- メモ化再起参考にさせていただきました。https://zenn.dev/sena21/articles/d64aa8b5d10e13
- 動的計画法とそうでは無い例について参考にさせていただきました。https://zero2one.jp/learningblog/dynamic-programming-python/
- 私が初めて見たナップサック問題の解説動画です。概要についてはこれで理解しました。https://youtu.be/oB3L8yyHsFY?si=OsX2tbHRfIgsXEbA
- 私的最強の動的計画法解説動画です。概要から実装まで分かりやすく、これ見て学んだと言っても過言では無いです。https://youtu.be/gVJ16ThsJYs?si=WCPR1Wtdt377pimi