 # memoization

(algorithmic technique)

Definition: Save (memoize) a computed answer for possible later reuse, rather than recomputing the answer.

Note: The term comes from "memo": "A short note written as a reminder." [The American Heritage Dictionary of the English Language, © 1970, American Heritage Publishing]

A naive program to compute Fibonacci numbers is

` fib(n) {    if n is 1 or 2, return 1;    return fib(n-1) + fib(n-2); } `
Because fib() is recomputed over and over for the same argument, run time for the above is Ω(1.6n). If instead we memoize (save) the value of fib(n) the first time we compute it, the run time is Θ(n).
` allocate array for memo; set all elements of memo to zero;  fib(n) {    if n is 1 or 2, return 1;    if memo[n] is not zero, return memo[n];    memo[n] = fib(n-1) + fib(n-2);    return memo[n]; } `

Of course, computing Fibonacci numbers can be easily done in logarithmic time (see Fibonacci numbers), but this illustrates memoization.

Author: PEB

## Implementation

Mark Nelson's tutorial to using C++ Hash Table Memoization: [for] Simplifying Dynamic Programming (C++).