DPの話 (追記)
前回の記事に対してみやむーさんから素晴らしい反響を頂いたので、こちらにレスポンスする形で追記してみます。
そもそも前回の「DPの話」は、こちらのエントリと内容が全く同じなのでした。全然気付いてなくてごめんなさい・・・。
ループのメリットとメモ再帰のメリット
「メモ再帰のメリットは計算が遅延的に行われること」とのことでした。メモ再帰では、「最終的に求めたい状態には絶対に遷移し得ないノード」への計算は行われません。そのようなノードが数多くある問題では、メモ再帰が速くなりうる。なるほど。
似たようなことがループでは絶対できないというわけではありません。配るDPにおいて、配る元のノードの値が初期値 (最短経路だったら inf とか、経路数だったら 0 とか) のままだったら、配っても意味が無いのでやめる。このような枝刈りを加えると、「初期状態から絶対遷移しないノードから」の計算は行われません。
が、メモ再帰のいいところは、それを特別にコーディングしなくても自然とそうなってくれるところにあります。if 文をいっこ入れないといけないループに比べて、これは明らかなメリットです。
ちなみに、イロモノ要因と思われたBFSによるDPでも、また別の枝刈りを考えることができます。こないだのコイン両替問題のBFS実装にちょっと付け加えましょう。
struct state{ int n, cost; }; int minChange(vector<int> value, int n){ vector<int> cost(n + 1, inf); queue<state> qu; for(qu.push((state){0, 0}); !qu.empty(); qu.pop()){ state st = qu.front(); if(cost[st.n] <= st.cost) continue; cost[st.n] = st.cost; if(st.n == n) return st.cost; // ここ！ for(int i = 0; i < value.size(); ++i){ if(st.n + value[i] <= n){ qu.push((state){ st.n + value[i], st.cost + 1 }); } } } return cost[n]; }
こうすると、答えが見つかった瞬間にBFSが終了するので枝刈りが効いてきます。私がこれを知ったのはLayCurse先生の記事で、私は普通のDPで突撃して死んでいたのでした。
