require 'benchmark'

class TriBonacci
  def initialize
    @memo = [1,1,2]
  end
  def f(n)
    return @memo[n] unless @memo[n] == nil
    @memo[n] = f(n-1) + f(n-2) + f(n-3)
  end
  def calc(n)
    last = @memo.length - 1
    return @memo[n] if n <= last
    (last + 1).upto(n-1) do |i|
      f(i)
    end
    f(n)
  end
end

n = 6500
Benchmark.bm do |x|
  x.report {TriBonacci.new.f(n)}
  x.report {TriBonacci.new.calc(n)}
end