an optimization technique used primarily to speed up computer programs by storing the results of expensive function calls and returning the cached result when the same inputs occur again. - wikipedia

see also Dynamic Programming

Fibonacci

Using it reduce the complexity of $fib(n)$ from $O(2^n)$ to $O(n)$, keeping space $O(n)$.

def fib( n)
   if (@f ||= []) && @f[n]      # memoize value exists
   elsif( n <= 2)               # else compute it
        @f[n] = 1
   else 
        @f[n] = fib( n-2) + fib( n -1)
   end

   @f[n]
end

n = 1000 # gets.to_i
puts [*0..n].map {|n| fibo(n)}.join(" ")