メモ化と動的計画法

# 素直にフィボナッチ
def fib_normal(n)
  return 1 if n == 0 || n == 1

  fib_normal(n - 1) + fib_normal(n - 2)
end

# メモ化
# 再帰の結果を配列に保存
# あくまで再利用がメイン
$memo = []
def fib_memo(n)
  return $memo[n] = 1 if n == 0 || n == 1
  return $memo[n] if $memo[n]

  $memo[n] = fib_memo(n - 1) + fib_memo(n - 2)
end

# 動的計画法
# 下から配列を埋めていく
# 次を求めるのに前の結果が必要
$dp = []
def fib_dp(n)
  $dp[0] = 1
  $dp[1] = 1
  (2..n).each do |i|
    $dp[i] = $dp[i - 1] + $dp[i - 2]
  end
  $dp[n]
end