#18 Recursion: Fibonacci Numbers
入力される数値nに対して、n項のフィボナッチ数を求めて出力する問題。
solution
問題文の通りに実装すると以下のようになる。
def fib(n) return n if n <= 1 return fib(n-1)+fib(n-2) end puts fib(gets.to_i)
これは正しいが、計算量が大きくなり、テストケースをパスできない。
今回はメモ化することでフィボナッチ計算を高速化する。 以下rubyでの解答。
class Solution def initialize @memo = [0, 1] end def fib(n) return if n < 0 return @memo[n] if @memo[n] return @memo[n] = self.fib(n - 1) + self.fib(n - 2) end end puts (Solution.new).fib(gets.to_i)
