DPとかメモ化再帰とか
以下の内容は間違いを含んでる可能性が高い。
状態数が少ない問題ではDPやメモ化再帰による解法が結構あるけど、少し整理してみよう。
まず、大前提としてDPやメモ化再帰が使える必要条件はDAGになっていることだろう。ここで考えているグラフは、各状態を頂点、状態遷移を有向辺としたグラフである。確率とかの問題だと辺に遷移確率の重みがつくと考えれば良い。
特に、最小値を求める系の問題では必要十分と言ってもいいかもしれない(何か三角不等式っぽいのが成り立っていればいいような気がする。でも組み合わせの数を求める系だと上手く行かないのでやっぱり嘘か？)。
DPというのは、DAGに対してトポロジカル順序の小さい順に値を決定していくことに他ならない。
メモ化再帰というのは、もらうDPの特殊形式で余計な所を評価しないlazyなアルゴリズムと言えるかもしれない。
こうして書いてみると、DPの欠点が明らかになる。それは、トポロジカル順序が分かりにくい時にどの順番に更新すればいいか分からないことである。これに対する対策は、
でもトポロジカル順序を考えなくても良いメモ化再帰が完全に上位互換であるかと言えば、もちろんそんなことはない。メモ化再帰は普通に書いたら深さ優先になることに注意しよう。それを踏まえてメモ化再帰のパッと思いつく欠点は、
- スタックオーバーフローの可能性がある。
- 配列の再利用ができない。
- 関数呼び出しのオーバーヘッドが重い。
特に配列の再利用についてはメモリ不足で解けなくなる問題が相当数あるので深刻な問題になりうる。
DAGだといつでもDPできる？
上でちょっと触れたように、確率とか、組み合わせの数を求めるようなDPでは話が単純でなくなる。
例えば、状態が次のようになっているとき、
状態1から4への3本のパスで、組み合わせだと互いに重複がないかとか、確率なら独立云々かんぬんとか、色々気にしてやらないといけないような気がする。
おまけ
状態間を表現したグラフがDAGにならないときは連立(1次)方程式になるし、自己ループの辺を取り除いたらDAGになるようなものはもっと単純な(1次)方程式になる。特に後者は確率の問題でよく見かける気がする。
おまけ2(何度か書いてることだけど)
ビットDPで、配る先がスーパーセットになっているようなもの(あるいは、貰う相手が部分集合になっているようなもの)は、forループを単純に0から(1<
追記(2011/7/30)
「DPというのは、DAGに対してトポロジカル順序の小さい順に値を決定していくこと」とか書いたけど、ゲーム木探索を忘れていた。ゲーム木探索だと逆にトポロジカル順序の大きい所から決定することになる。
