【アルゴリズム】動的計画法(DP)をまとめて使い方を解説してみた：競プロにも必須のアルゴリズム動的計画法dp

今回は、競技プログラミングを始めたばかりの人向けに「DP(動的計画法)」について書いていこうと思います。
まだ、プログラミング自体触れたのが初めての人は少し内容が難しいので、他の記事で初心者向けのを書いているので、そちらを見てからぜひこの記事を読んでください。

DP(動的計画法)とは

DPとは、DynamicProgrammingの略です。

まずは定義から、恒例のWikipediaさんからの引用

細かくアルゴリズムが定義されているわけではなく、下記2条件を満たすアルゴリズムの総称である。
１．帰納的な関係の利用：より小さな問題例の解や計算結果を帰納的な関係を利用してより大きな問題例を解くのに使用する。
２．計算結果の記録：小さな問題例、計算結果から記録し、同じ計算を何度も行うことを避ける。帰納的な関係での参照を効率よく行うために、計算結果は整数、文字やその組みなどを見出しにして管理される。

ちょっと難しい言葉ばかりなのでめちゃくちゃ簡単に説明すると

１．分割統治法

２．メモ化再帰

といった感じです。

1については、例えば漸化式などが当てはまるでしょう。漸化式については、高校数学でで習う内容なので詳しくは説明しませんが、要は数列と数列の関係性です。

例えば、掛け算とかもそうですね

a(n+1)=2a(n)+2

このように、状態の遷移を頭の中でイメージが出来るようになれば、基本的なDPは、もう理解できているといえるでしょう。

メモ化再帰というのは、再帰関数を利用したもので、一度計算したものを名前の通りメモしていき、同じ計算をしないようにするといったものです。そうすることによって、もう計算したところは計算せず、値を返すだけになり計算時間が短くすることが出来ます。

とりあえずはそういうものという感じだけつかめればオーケーです。

なぜ動的計画法（DP）を使うのか

まぁ簡単な話、計算時間が短縮できるというのが狙いですね。

分割統治法を使うことによって、大きな問題を簡略化して示すことが出来るので、そういった側面での使い方もありそうですね...

自分は、計算時間短縮以外で使ったことないですが...w

例題で実践！

例題をやって、理解を深めていきましょう

１．フィボナッチ数列

DPの例題として一番有名なのが、このフィボナッチ数列です。

この問題を通して、どのように解いていくのか具体的に説明しながらやっていきます。

まず、フィボナッチ数列とは何か
数字だけ挙げると、
0,1,1,2,3,5,8,13,21,34,55....
っていうやつですw
今回は、これの意味とかは考えずに数字だけ使っていきます。

STEP1 漸化式をたててみよう

今回は、もう一般的に知られている漸化式なので、答えは皆さん知っているかと思うので、導き方はスキップします。

STEP２　DPテーブルを考えてみる

DPテーブルは、簡単に言うと表みたいなやつです。

値がどう動いていくのかを具体的に知ることが出来ます。

今回は、一次元配列なのですごくイメージしやすいかと思います。

配列の要素数	０	１	２	３	４	５	６	７
値	０	１	１	２	３	５	８	１３

こんな感じに値が遷移していきます。

一つ一つ見ていくと漸化式が正しいことがわかりますね。

STEP3　Let's programming！

#include <stdio.h>

int main(){
	int dp[10];
	dp[0]=0;
	for(int i=1;i<10;i++){
		if(i==1 || i==2)dp[i]=1;
		else dp[i]=dp[i-1]+dp[i-2];
	}

	for(int i=0;i<10;i++){
		printf("%d\t",dp[i]);
	}
	return 0;
}

こんな感じになりましたでしょうか？

書き方にはいろいろあるので、とりあえず実行結果を見てみましょう。

今回は、10回にしているので

0  1  1  2  3  5  8  13  21  34

こうなるかと思います。
流石に簡単すぎますねw

今度はもっと実践的なものをやってみようと思います。

2. ナップサック問題

ナップザック問題とは、

容量 C のナップサックが一つと、n 種類の品物（各々、価値 p_i, 容積 c_i）が与えられたとき、ナップサックの容量 C を超えない範囲でいくつかの品物をナップサックに詰め、ナップサックに入れた品物の価値の和を最大化するにはどの品物を選べばよいか」という整数計画問題である。同じ種類の品物を1つまでしか入れられない場合（x_i ∈ {0, 1}）や、同じ品物をいくつでも入れてよい場合（x_i ∈ 0以上の整数）など、いくつかのバリエーションが存在する。

では、問題

価値が v_i 、重さが w_i であるような N 個の品物と、容量が W のナップザックがあります。次の条件を満たすように、品物を選んでナップザックに入れます：

選んだ品物の価値の合計をできるだけ高くする。
選んだ品物の重さの総和は W を超えない。

価値の合計の最大値を求めてください。

この問題は有名なオンラインサイトのAIZU ONLINE JUDGEの問題で、提出もできるのでプログラムを書いて提出もしてみましょう。

それでは、解き方

STEP1 漸化式を考えよう

どのように値が更新されていくのかを考えましょう。
まず、先ほどと同じように考えてみます。

dp[i+1]=:i番目までの品物の中から、重さがWを超えないように選んだ価値Vの最大値

一見よさそうに見えますが、これだとdp[i]に対して、品物(価値、重さ)を加えるかどうかを考えるとき、加えた時に重さがWを超えているかどうかがわからないので、ダメです。
式にWに関する部分がないですもんね。だから、この式に必要なのは現状重さWがどうなっているかという情報です。それを考慮して考えると式は以下のようになります。

dp[i+1][w]=:i番目までの品物の中から重さWを超えないように選んだ価値Vの最大値

Wの部分は重さに関係することろですね。

dp[i+1][w]を求めるには以下のとおりです。

・品物を選ぶ場合(W>=weight[i])

dp[i+1][w]=dp[i][w-weight[i]]+value[i]

・品物を選ばない場合

dp[i+1][w]=dp[i][w]

となる。

よって、漸化式は

dp[i+1][w]= $d p [i + 1] [w] = {\begin{cases} max (d p [i] [w - w e i g h t [i]] + v a l u e [i], d p [i] [w]) & (w \geq w e i g h t [i]) \\ d p [i] [w] & (w < w e i g h t [i]) \end{cases}$ (w>=weight[i]),dp[i][w]

となる。

初期条件は、dp[0][w]=0

STEP2 DPテーブルを考えてみよう

二次元配列なので、少し難しいかもしれませんが要は

dp[i][w]=:i番目(i回目)に重さを超えないよう選んだ最大の価値

なので、難しく考えることはないです。

ここまではっきりと頭の中に思い浮かべなくてもいいです。

こんな感じかなぁぐらいで大丈夫です。

あとは、もうプログラムを書くだけですね。

今回はせっかくですので、提出もできるということなのでプログラムを自分で書いて提出してみましょう。

それでは、今度はもう少し競プロっぽい問題をやりましょう

3. ABC040_C

この問題は、Atcoderの問題です。こちらも提出ができるので是非やってみましょう。

問題

$N$ 本の木の柱が左から右へ一列に並んだアスレチックがあります。左から $i$ 本目の柱の高さは、a[i]センチメートルです。
高橋君は左から $1$ 本目の柱からスタートし、右へ柱を渡っていき $N$ 本目の柱まで行こうとしています。
高橋君がある柱にいるとき、次には現在の柱から $1$ 個もしくは $2$ 個右にある柱のどちらかへ移動することができます。
移動するときには、現在いる柱の高さと、移動後の柱の高さの差の絶対値のぶんだけコストがかかります。
$N$ 本目の柱まで行くとき、コストの合計の最小値はいくらになるでしょうか。

この問題は、基本的なDP問題です。先ほどのナップサック問題よりも簡単ですので軽くやっていきましょう。

これは一次元配列でことたりるので、イメージがしやすいですね。

一本目からスタートということなので、dp[1]=0ですね。

漸化式を考えるのは簡単ですが、今回の問題は少し違う点があってそれは後ろから考えていくことです。
dp[i+1]にしてしまうと、iと自分がいる位置を関連付けているのでi+1は一個右に行く動作と一緒になってしまい、うまくいかなくなってしまいます。
ですので、ならば逆に後ろからやっていけばいいということで、以下のようにします。

dp[i]=:着地地点がi番目の木のときのコストの最小値

dp[i]=min(dp[i-2]+|a[i-2]-a[i]|,dp[i-1]+|a[i-1]-a[i]|)

となります。
絶対値ですので、すごく簡単かと思います。

3.ABC129_C

こちらもAtcoderさんの問題です

問題

$N$ 段の階段があります。高橋君は現在、上り口( $0$ 段目)にいます。高橋君は一歩で $1$ 段か $2$ 段上ることができます。
ただし、 $a_{1}, a_{2}, a_{3}, . . . . a_{M}$ 段目の床は壊れており、その段に足を踏み入れることは危険です。
壊れている床を踏まないようにしながら、最上段( $N$ 段目)にたどりつくまでの移動方法は何通りあるでしょうか？
総数を $1, 000, 000, 007$ で割った余りを求めてください。

こちらの問題も一見難しそうに見えますが、よくよく考えて見るとフィボナッチ数列の時と一緒だということがわかります。

例えば、x>=2のとき、x段目にたどり着く方法は、

・x-2段目から二段上がる

・x-1段目から一段上がる

この二通り存在します。これを繰り返していくと最上段まで登る移動方法がわかります。さきほどいった逆から考えて見るのと考え方は似ていますね。

あとは、条件にもある通り、穴a[i]に気を付ければ大丈夫ですね。

dp[i]=:i番目の板に到達する移動方法の数

漸化式は、以下のようになります。

dp[i]=dp[i-1]+dp[i-2]

そして、問題にもある通り1000000007で割ったあまりということで、注意です。

最後の答えだけを1000000007で割るのではなく、計算している段階で割っていきましょう。
そうしないと答えがずれてしまう場合があります。
今回の問題だけでなく、こういうmodを使う問題は、更新するときに割っていきましょう。

4.ARC075_C

問題

あなたはコンピュータで試験を受けています。試験は N 問の問題からなり、i 問目の問題の配点は s_i です。それぞれの問題に対するあなたの解答は「正解」または「不正解」のいずれかとして判定され、正解した問題の配点の合計があなたの成績となります。あなたが解答を終えると、解答がその場で採点されて成績が表示される…はずでした。
ところが、試験システムに欠陥があり、成績が 10 の倍数の場合は、画面上で成績が 0 と表示されてしまいます。それ以外の場合は、画面に正しい成績が表示されます。この状況で、成績として画面に表示されうる最大の値はいくつでしょうか？

この問題は、正攻法で解くと

まず、すべての配点の合計をSとして、

・Sが十の倍数でない場合は、その点数が画面に表示できる最大の成績

・Sが十の倍数である場合、画面に0でない成績を表示するにはどれか不正解にする必要があり、もし、配点が10の倍数でないような問題が一問以上存在するならその中で一番配点が低い問題を不正解にすればいい。全部配点が十の倍数だったら、画面に0が表示される。

ですが、せっかくですのでDPで解いてみましょう。

簡単に言うとDPを使って、解いた可能性のある合計点をすべて列挙するということです。

今回は二次元配列を使います。今回はbool型で行きます。

dp[i+1][j]=:i問目までの中でとることができる点数の合計点

dp[i+1][j]={max(dp[i][j],dp[i][j-s[i]])(j>=s[i]),dp[i][j](j<s[i])}

初期値の設定は、とりあえず

・0点のところ

・一番最初の値のところ

でいいのではないでしょうか

一番最初の値のところだととるか取らないかで、合計点は0点かその一番最初の値の二つしかないので、初期値として設定してもいいでしょう。

そして、これを最後まで更新していくと、dp[n][i]にその問題でとりうる可能性のある合計点がすべて列挙されているので、あとはそのdp[n][i]を一つ一つ見とけば答えにたどり着くようになっています。

その際に少しテクニックを使うと計算時間が短くなります。何かというと今回使うdpはjの部分と数字の合計値を関連付けています。言うなればパケット法見たく、1000という合計値になったら[1000]の配列に1が入るといった感じです。
なので、最大値を見つけるとき後ろからチェックしていき、10の倍数以外で一番最初にその条件にあった値があったら、その時点でbreakして大丈夫です。

そして、もう一つ注意事項がありまして、制約をこの記事には記載していないんですけど、この問題は、

・1<=N<=100

・1<=si<=100

ということなので、合計値がとりうる最大の値は10000です。

これを静的に配列で確保しようとすると、できません。

なので、宣言するときに

static int dp~

とstaticを前につけてください。

そうすれば大丈夫です。

まとめ

と、まぁこんな感じで例題をいくつか紹介してきました。

まだまだDPには奥があります。

区間DP、bitDP...etc

興味のある方は是非挑戦してみてください