メモ化再帰

本物のページはこちら→memoization

Included page "memoization" does not exist (create it now)

動的計画法再帰的に使ったものらしい。

同じ場所に、違う経路からたどり着いた場合、
複数の経路を数えるのが無駄だよね。
そういう無駄を
深さ優先探索を、メモ配列を使って無駄な計算の2度手間を省いたものである。

ポリシー

  • 1度計算したものは2度計算しない

1度目は普通に計算して、2度めからは特別な処理を行えば良い。

  • なるべく狭い範囲でメモするように工夫する

じゃないと、計算量で損してるかも!

やり方

探索結果をメモできる配列を用意しておく。
その配列にメモする値は、その結果にたどり着くまでに何通りあるのか
そして、同じノード(というか同じ結果)に再び来た場合は、そのメモした値を返してあげる。そうやって2度計算することを防ぐ。

何をメモすればいい?

一回計算したところを二度も計算したくない、が目的だから、再帰の計算結果をメモする

どんな時に使う?

  • 複数の親を持つ子がいるようなツリーになっちゃった場合

  • 格子になってて、同じ場所を何回か通る可能性がある場合

  • 違う組み合わせだけど、結果の値が同じになるようなものが出るような場合(例:ナップザック問題

サポートサイト Wikidot.com