DPとメモ付き探索

なんか最近練習している暇がない(というわけでもないけれどやっていない)ので、やっていて思うことを少しだけ書き残しておこうかなぁと。厳密な意味では正しくないことを言っているのだけれど、自分の中では整理できていないことを整理するために。

最初の前提として、DPは苦手です。TopCoderがDPにカテゴライズしているものの成績がそこまで悪くないのは、DPではない方法で解いているとか、それ以前にグラフやら幾何やらがもっと悪いとか、そういった諸事情があるように思います。

DP

DynamicProgramingの略。何がDynamicなのかはいまいち良く分からないけれども...。要はこれ、一番小さいサイズで問題を解いて、その結果を利用して一回り大きい問題を解いて...とやって最終的に必要なサイズの問題を解く、ということ。ボトムアッププログラミングをするということ。もちろんフィボナッチくらいなら書けます。

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

で、DPが得意かどうかという問題は、普段プログラムを書いているときに、どうやってプログラムを書きますか、という問題に通ずるところがあると思います。さらにいうと、あなたはmain関数をいつ書きますか、ということ。ぼくは常に最初に書きます。

当然ながらプログラミングはmain関数だけで終わりません。計算の流れに応じて必要になったものを、必要になったときに、サブルーチンとして書いていきます。これはトップダウンプログラミングです。残念ながらDPとは逆行しそうです。(世の中には投機的に必要そうなサブルーチンを先に作って全体を"過不足なく"組み上げるという神がかった人もいるようです。そういう人はDP"も"得意なことでしょう。というか何やらせてもいいと思うんだ。)

メモ付き探索

で、もうトップダウン脳だからボトムアップなDPは解けないよ、と諦める前に...。DPでボトムアップにできるってことは、うまいことやればトップダウンにも解けるはず、と思うことにしましょう。これがメモ付き探索。試しにフィボナッチを書いてみる。

int memo[] = new int[size];
int fib(int n) {
  if( n < 2 ) { return 1; }
  if( memo[n] != 0 ) { return memo[n]; }
  return memo[n] = fib(n-1) + fib(n-2);
}

何をしているのかというと、問題を解く際に、必要になる部分要素を順次求めていくという作業を、同じ値を再計算しないようにメモしてるというもの。これに加えてみる必要のないものを切り捨てる枝狩りとかもできるし、DPと違って必要にならないものを事前に計算したりもしない。(その分ルーチンが煩雑になることもあるけど。)

DPでできる人にとっては、どっちも同じじゃん、というような感じではありそう。某G社の面接でフィボナッチについて色々と聞かれることもあるらしいので、きっとDP>メモ付き探索なんだろう。(関係ない。)

最後に

取り敢えずDPで解くべき問題を見かけたら、メモ付き探索で解いているように思います。自明にDPできそうなのはDPしていると思いますが。後、メモリが足りないケースは仕方なしにDPしていると思う。(N枚のテーブルは持てないけれど、近隣の2枚をフリップしながらというようなやつ。メモ付き探索だと行ったり来たりするはずなので、余計直観的じゃなくなりそう。)

引数がintの範囲ならフィボナッチはintから溢れるじゃないか、みたいな突っ込みはスルーの方向で。(そもそもintの範囲でテーブル取れないって。)メモ付き探索でfibの値がたまたま0になったりするとひどいことになるんじゃないか、という気が一瞬したけれど、0がずっと続くことはないし、かなりの間隔でしか出ないだろうから問題にはならないはず。ちなみに0が入ってる部分では、従来通り2分岐するので、0の入る場所の数だけ指数的に広がるけれど、intの範囲でいくつあることやら。最近の計算機なら50個くらいなら終わると思う。呼び出しフラグ持ってもいいかもね。

取り敢えずコーディングスタイルとしては、ボトムアップよりもトップダウンの方が好きです。Greedyに欲しいものを書いていくのが性にあっているんだと思う。(なんか250と500くらいなら解けるくらいgdgdしてたような気もする。)