動的計画法（dp）の漸化式の意味を例と共に詳しめに説明してみる。
今回は、いわゆるナップサック問題を解く際に用いられる動的計画法のコードの動きが個人的に分かりづらかったので、自分の頭の中を整理する意味も込めて解説してみる。
まずは、ナップサック問題ってなんやねん？という人もいるかもしれないので、ナップサック問題の例を載せときます。
問題
重さと価値がそれぞれw_i,v_iであるようなn個の品物があり、これらの品物を重さの総和がW以下となるように選んだ時の価値の最大値は？
入力
n W
w_1 v_1
w_2 v_2
：
w_n v_n
さて、この問題を解くと、下のようなコードになります（Java）。
import java.util.*;
public class Main{
public static void main(String args){
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int W = sc.nextInt();
int w = new int[n];
int v = new int[n];
//dpテーブル
int[] dp = new int[110][10010];
for(int i = 0; i < n; i++) {
w[i] = sc.nextInt();
v[i] = sc.nextInt();
}
//初期条件
for(int i = 0; i <= W; i++) {
dp[0][i] = 0;
}
//dpの処理
for(int i = 0; i < n; i++) {
for(int j = 0; j <= W; j++) {
if(j>=w[i]) {
dp[i+1][j]= Math.max(dp[i][j-w[i]]+v[i],dp[i][j]);
}
else {
dp[i+1][j]=dp[i][j];
}
}
}
System.out.println(dp[n][W]);
}
}
このコードを書く上で、考え方の核となっているのは次の漸化式です。
dp[i+1][j] = max(dp[i][j-w[i]] +v[i],dp[i][j]) (j>=w[i]),
dp[i][j] (j<w[i])
この漸化式をfor文でループさせているわけだが、ループを1周する間にどんな処理をしているかを下の写真を使って紐解いてみようと思う。
注：表のｗはコードのループ内のjにあたります。
では、i=3、j=3を求めるまでの過程を見てみます。
まず、上の漸化式にそのまま当てはめてみると、
dp[3][3] = max(dp[2][3-w[2]] +v[2],dp[2][3]) (3>=w[2]),
dp[2][3] (3<w[2])
となります。ぱっと見、ちょっとややこしい。実際に1個1個見ていきましょう！
まず、dp[3][3]を求めるためにはdp[2][3]の情報がいります。というわけで、dp[2][3]を見てみましょう。そうすると、5という数値が入っています。そして、今回のｊは品物の番号なので、今回見ている品物は上から2番目のw[2]=3,v[2]=6のヤツです。品物の重さが今見ているｊ（重さの上限）以下なので持っていけます！ただ、この品物を運んでしまったことで重量超過しちゃアカンので、重さがｊ－３の状態（今回は３－３＝０）での価値ｖを参照する必要が出てきます（この品物の重さを足し合わせるとちょうどｊになるから）。dp[2][0]は0なので、dp[3][3] = max(0+6,5)=6
このようにして、品物3を選び、重さの上限が3である際の価値の最大値が得られます。この処理をず～っとdp[1][0]を求める段階から続けているので、常に価値は最大となります！
最後に
この記事を書くことで、少しは頭がすっきりした気がします。動的計画法は何かを最大化したいときに使うそうなので、これからもしっかり自分一人で書けるように頑張っていきます！
参考にさせて頂いた記事
