動的計画法を復習
LeetCode #5 の動的計画法を使った解法を実装しようとしたが、体系的に?復讐しておきたかったので。動的計画法は、再帰を使って解くような繰り返し小さい問題を再帰的にに解くような問題において、メモ化することで計算時間が指数関数的に爆発するのを避ける手法。(Wikipedia)
ボトムアップとトップダウンに実装する2パターンがあるということで、トップダウンのほうが見慣れている(7年前にもやってた)。再帰呼び出しになってしまうところで、メモ化しておいた結果を再利用。ボトムアップは文字通り下から結果を積み上げていく感じだ。
def fib_bottomup(n) memo = {0 => 1, 1 => 1} i = 2 while i <= n do memo[i] = memo[i-1] + memo[i-2] i += 1 end memo[n] end @memo = Hash.new def fib_topdown(n) if n <= 1 @memo[n] = 1 elsif @memo[n] @memo[n] else result = fib_topdown(n-1) + fib_topdown(n-2) @memo[n] = result end end def fib(n) if n <= 1 1 else fib(n-1) + fib(n-2) end end %w(10 20 30 40).map(&:to_i).each do |i| puts fib_bottomup(i) puts fib_topdown(i) puts fib(i) end
これを文字列の問題に適用するのが、まだサクッとできない。