Memoization – The Top-Down Approach

No, this is not "memorization," though that would also describe this technique quite accurately. Using memoization, we can reformulate the top-down solution we described previously to make use of the optimal substructure property exhibited by the Fibonacci sequence. Our program logic will essentially be the same as it was before, only now, after having found the solution at every step, we will cache the results in an array, indexed according to the current value of n (in this problem, n represents the state or set of parameters defining the current recursive branch). At the very beginning of each function call, we will check to see whether we have a solution available in the cache for state F(n). If so, we will simply return the cached value:

const int UNKNOWN = -1;

const int MAX_SIZE = 100000;

vector<int> memo(MAX_SIZE, UNKNOWN);

int Fibonacci(int n)

{

    if(n < 2)

    {

    ...