第弐回プロコン分科会(動的計画法(DP)のはなし)

その前に

マラソンマッチが今朝方から始まりましたね。
TopCoder

その他(競プロのこつシリーズ)

テンプレート(repとか)を作ろう
メモリを多めにとったり番兵を活用したりしてコードを書きやすくする
人のコードを見ると発見があってよい

動的計画法その前に

まず、大前提ですが、普通の全探索(やるだけ)は書けますよね？？？(僕が書けるとは言っていない)
(全探索だと計算量がえらいことになる→動的計画法、という流れなので、まずは全探索で問題がちゃんと解けるようになりましょう)

動的計画法(DP)

問題例

AOJの入門のやつ
フィボナッチ数列 | アルゴリズムとデータ構造 | Aizu Online Judge
Online Programming Lesson (いろいろなDP問の入門)
連鎖行列積 | アルゴリズムとデータ構造 | Aizu Online Judge(行列についての知識がないと難)

やや難
bookshelf: 本棚 (Bookshelf) - 2011年日本情報オリンピック春合宿OJ | AtCoder
http://www.ioi-jp.org/camp/2011/2011-sp-tasks/2011-sp-day4.pdf (bookshelfの問題はこのpdfに載ってる)
chopsticks: 塗り箸 (Chopsticks) - 2009年日本情報オリンピック春合宿OJ | AtCoder
http://www.ioi-jp.org/camp/2009/2009-sp-tasks/2009-sp_tr-day4_23.pdf (chopsticsの問題)
lake: 湖 (Lake) - 2010年日本情報オリンピック春合宿OJ | AtCoder
http://www.ioi-jp.org/camp/2010/2010-sp-tasks/2010-sp-day4_23.pdf (lakeの問題)

ほかにも問題名を僕に投げてくれれば、(dpである|dpでない|知らない)を返します。

とりあえずこちらをご覧ください

フィボナッチ数列の第n項を返す関数fib(n)をつくる

単純な全探索

int fib(int n){
  if(n<=1)return 1;
  else return fib(n-1)+fib(n-2);
}
//これだと、だいたいO(1.6^n)かかる。つらい。

メモ化再帰

int memo[100005]={};
int fib(int n){
  if(memo[n]>0)return memo[n];
  //各nに対して、これ以降が呼び出されるのはたかだか一回
  if(n<=1)memo[n]=1;
  else memo[n]=fib(n-1)+fib(n-2);
  return memo[n];
}

動的計画法

int dp[100005];
void init(){
  dp[0]=dp[1]=1;
  for(int i=2;i<100000;i++){
    dp[i]=dp[i-1]+dp[i-2];
  }
}
int fib(int n){
  return dp[n];
}

各々の利点として、
メモ化再帰 .. 再帰を改変するだけなので初めての人には実装が楽
DP .. わりと高速。あと、最長増加部分列のO(logn)解法は配列でないとダメ
ですかね。

なぜdpでうまくいくか

よくある事例

ナップサック問題

Q.

0-1 Knapsack Problem | Aizu Online Judge
N個の商品があり、各々に重さC_iとうれしさA_iが決まっている。N個のうちから重さの合計がK以下になるように商品を選んだ時の嬉しさの総和の最大値を求めよ。

最長増加部分列問題

Q.

最長増加部分列 | 動的計画法 | Aizu Online Judge
長さnの数列A_1...A_nが与えられるので、単調増加な最長の部分列(連続でなくてもよい)を求める

解き方

で、DPの問題は漸化式を作れれば解けます。
例) dp[i] = max{dp[k]+1 | k < a[i] }
とか。
dp配列の定義をしっかりしておかないと、デバッグのときに苦しむことになります。(dp[i][j]には何が入るべきなのか)
あと、添え字とか初期化の値とかには要注意。
たいてい、デバッグは配列を吐き出して行うイメージ。

Q.

漸化式が思いつけないんですが

A.

僕も漸化式の状態では思いつけません...(数学が強い人は数式をいじって解いたりしている)
簡単に埋められて答えの得られるようなうまい配列を思いつく、みたいな感じでやってます。

Q.

そもそもDPの問題だと見抜けないんですが...

A.

経験値でがんばって見抜いてください...
(もっとよい判断方法があるのかもしれないけど僕にはわからない...)

よくある事例

ナップサック問題

蟻本が優秀なのでそれ読んで。

A.

値段が同じになるような商品の取りかたなら、そのうち嬉しさ度が最大のものだけ覚えておけばよい、という性質を利用する。
または、
嬉しさ度が同じになるような商品の取りかたなら、そのうち値段が最小のものだけ覚えておけばよい、という性質を利用する。

最長共通部分列

最長増加部分列

蟻本を読んでくださいと言った感じ(口頭でするかも)

A

増加しているかどうかは、最後の数字さえ憶えておけば判定できる、という性質を利用する。
与えられた数列をa[0],a[1]...とします。

dp[i] .. 数列のi番目の数字が最後に来るような部分列の最長の長さ、とすると、
dp[i] = min{ dp[k]+1 | a[k] < a[i] }
これだと、コードは

for(int i=0;i<n;i++){
  dp[i]=1;
  for(int k=0;k<i;i++){
    if(a[k]<a[i])dp[i]=max(dp[i],dp[k]+1);
  }
}
printf("%d\n",dp[n-1]);

となって、O(n^2). n=10^5とかだとつらい。

dp[i][p] .. 数列のi番目の数字までを用いた時、数字pが最後に来るような部分列の最長の長さ、とすると、
dp[i][p] = a[i]==p ? min{ dp[i-1][k]+1 | k < a[i] } : dp[i-1][p]
なんやかんやで、

fill(dp,dp+n,inf);
for(int i=0;i<n;i++){
  dp[a[i]] = max{ dp[k] | k < a[i]} + 1
}

で、これだと、普通はO(n^2)になるが、
maxを取るときにSegtreeとかを使うと、maxを取る操作がO(logn)になるので、n=10^5とかでもいける。
(メモ化再帰でするとセグ木との相性がよくないかな)

ビットDP

dp[105][2][2][2][2][2][2][2][2][2][2]; みたいな配列が生えるとやばそうなのでbitで状態管理しましょうねという話。

木DP

グラフのときに触れるかも
(というか、グラフの最短経路を求めるアルゴリズムはたいていDPっぽい)

区間DP

Q.

力持ち | Aizu Online Judge
これとか。
dp[i][j] = max{ dp[i][k] * dp[k][j] + a[k] | i

桁DP

確率DP

確率漸化式はもろDPですね、という話。
注意する点として、たとえば、
dp[i] = sum{ dp[k] * r^(i-k) | 1 <= k < i}
みたいのが立ったとすると、

dp[1] = 1;
for(int i=2;i<n;i++){
  dp[i] = 0;
  double nr = r;
  for(int k=i-1;k>=1;k--){
    dp[i] += dp[k] * nr;
    nr *= r;
  }
}

みたいなのになって、これだとO(n^2)だが、答えの誤差が1e-6未満とかだと、nrが小さいのは無視してかまわなくなり、計算量が落ちる、みたいなのがあります。

数え上げDP

ほかにもいろいろなDPがあるよ！！！
(最近だと、monge性とかいうのを用いたmongeDPとかいうのがあるらしい)

参考

最強最速アルゴリズマー養成講座：アルゴリズマーの登竜門、「動的計画法・メモ化再帰」はこんなに簡単だった (1/5) - ITmedia エンタープライズ chokudaiさんの連載。僕はこれで動的計画法の概念を知った。入門向け。
プログラミングコンテストでの動的計画法 iwiwi大先生のスライド。よい。