動的計画法を復習

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

これを文字列の問題に適用するのが、まだサクッとできない。