競プロ初心者の中で、動的計画法が難しくて挫折する人は多く、そこに対するアドバイスは、「たくさんやって慣れるしかない」と言うものが殆どだ。
何故DPは難しいのか。
パターンが多くて、応用が効かないという声をしばしば目にする。
ならば、様々なパターンを細かく分類して、難易度順に並べて学習したら、少しは簡単になるのではないか？
そんな私の考えが上手くいくのか試みるのが、このページである。
蛙飛びパターン
DP学習において、多くの教材で最初に出てくるやつを、蛙飛びパターンと呼ぶことにしよう。私がそう言っているだけで、別の誰かがもっと良い呼び方をしているかもしれないが、他に知らないので、ここではそうしておく。
これはどのようなパターンかというと、1次元上で遷移がシンプルなDPの事だ。
例を挙げるなら、階段を1度に1段か2段上がることができる時、一番上まで行く経路は何通りかとか、そういうやつ。
dp[i]:i番目の場所にいる時に、ここまで来るのに何通りかとかの状態を持ち、遷移がdp[i]=dp[i-1]+dp[i-2]的な感じの。
「階段を1段か2段」ではなく、「マスをサイコロ(普通の6面)を振って出た数字の数だけ」だったら、dp[i]=dp[i-1]+dp[i-2]+dp[i-3]+dp[i-4]+dp[i-5]+dp[i-6]になる。
状態は何通りとは限らず、何かしらの最小値などの事もある。
その場合は、遷移もdp[i]=min(dp[i-1],dp[i-2])などに変わる。
ベースとしてdp[i]がdp[i-a],dp[i-b]…の値の演算によって決まる系は、同ジャンルとして扱う。
経路パターン
続いては2次元上のマスを進んでいくDP。
左上のマスを(0,0)、右下のマスを(n,m)として、左上から右下まで、右か下にしか進めないなら、経路は何通りかとか。
dp[i][j]:i行目のj列目のマスにいる時、ここまで来るのに何通りかみたいな状態を持ち、遷移がdp[i][j]=dp[i-1][j]+dp[i][j-1]的な感じの。
右か下の2通りにしか進めなければ、右辺は2つの足し算になるが、右か下か斜め移動(右下)の3通りだったら、dp[i][j]=dp[i-1][j]+dp[i][j-1]+dp[i-1][j-1]と、3つの足し算になる。
右には1マスしか進めないが、下には2マスまで進めるとかなら、dp[i][j]=dp[i-1][j]+dp[i][j-1]+dp[i][j-2]になるし、障害物があれば遷移できないなど、色々あるだろう。
求めるものが経路でなくても、マス目の値を元に計算していくタイプは、同ジャンルとして扱う。
スケジュールパターン
これも私が勝手にスケジュールDPと呼んでいるだけだが、実際にスケジュールを決める類のDPは低難度帯でよく出るので、割と分かりやすい分類になるのではないか。
例えば、「今から3日間、1日1食ラーメンか寿司かステーキしか食べないとして、そのような食事の決め方は何通りあるか、ただし飽きるので同じものを連続で食べることはできないとする」みたいなやつ。
ラーメン→寿司→ステーキはOKだけど、寿司→寿司→ステーキは寿司が連続してるのでNG。たかが3日なら、メニュー3種類なので、3^3を全探索すれば良いが、100000日とかになると3^100000で無理。
そういう時はdp[i][X]:i日目にX(ラーメンor寿司orステーキ)を食べる時、ここまで何通りかという状態を持ち、遷移は
dp[i][ラーメン]=dp[i-1][寿司]+dp[i-1][ステーキ]
dp[i][寿司]=dp[i-1][ラーメン]+dp[i-1][ステーキ]
dp[i][ステーキ]=dp[i-1][寿司]+dp[i-1][ラーメン]
(連続は駄目なので、dp[i][ラーメン]にdp[i-1][ラーメン]を足したりしてはいけない)
になって、最終日をNとするなら、答えはdp[N][ラーメン]+dp[N][寿司]+dp[N][ステーキ]の合計になる。
こんな感じで2次元のDPだけど、2つ目のキーの値が少ない物を(今回の例ならラーメン,寿司,ステーキなので、0~2まで値しか取らない。他の例として、直前でやったかやらないかだったら、0,1の値しか取らない)、スケジュールパターンとしてみた。
ここから更に部分和、ナップサックと続いていくが、とりあえず初心者は、ここまでやれば優し目のD問題くらいまでのDPは、コンテストでACできるようになるはず。
以降はその内、このページの表示回数を見て、需要がありそうなら書く。